Identifying codes and locating-dominating sets on paths and cycles

Details Identifying codes and locating-dominating sets on paths and cycles Identifying codes and locating-dominating sets on paths and cycles

2009-08-19

arxiv.org/abs/0908.2750v1

Mathematics

Combinatorics

Scientific paper

Let $G=(V,E)$ be a graph and let $r\ge 1$ be an integer. For a set $D \subseteq V$, define $N_r[x] = \{y \in V: d(x, y) \leq r\}$ and $D_r(x) = N_r[x] \cap D$, where $d(x,y)$ denotes the number of edges in any shortest path between $x$ and $y$. $D$ is known as an $r$-identifying code ($r$-locating-dominating set, respectively), if for all vertices $x\in V$ ($x \in V\backslash D$, respectively), $D_r(x)$ are all nonempty and different. In this paper, we provide complete results for $r$-identifying codes in paths and odd cycles; we also give complete results for 2-locating-dominating sets in cycles.

Affiliated with

Also associated with

No associations

Rating

Identifying codes and locating-dominating sets on paths and cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Identifying codes and locating-dominating sets on paths and cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Identifying codes and locating-dominating sets on paths and cycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-216403