Identifying codes and locating–dominating sets on paths and cycles

Let G = ( V , E ) be a graph and let r ≥ 1 be an integer. For a set D ⊆ V , define N r [ x ] = { y ∈ V : d ( x , y ) ≤ r } and D r ( x ) = N r [ x ] ∩ 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-dominatin...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2011-09, Vol.159 (15), p.1540-1547
Main Authors: Chen, Chunxia, Lu, Changhong, Miao, Zhengke
Format: Article
Language:English
Subjects:
[formula omitted]-identifying codes
[formula omitted]-locating-dominating sets
Algorithmics. Computability. Computer arithmetics
Applied sciences
Charon
Combinatorial analysis
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Cycles
Exact sciences and technology
Graphs
Information retrieval. Graph
Integers
Mathematical analysis
Mathematics
Paths
Sciences and techniques of general use
Sensors
Shortest-path problems
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G = ( V , E ) be a graph and let r ≥ 1 be an integer. For a set D ⊆ V , define N r [ x ] = { y ∈ V : d ( x , y ) ≤ r } and D r ( x ) = N r [ x ] ∩ 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 ∈ V ( x ∈ V ∖ D , respectively), D r ( x ) are all nonempty and different. Roberts and Roberts [D.L. Roberts, F.S. Roberts, Locating sensors in paths and cycles: the case of 2-identifying codes, European Journal of Combinatorics 29 (2008) 72–82] provided complete results for the paths and cycles when r = 2 . In this paper, we provide results for a remaining open case in cycles and complete results in paths for r -identifying codes; we also give complete results for 2-locating-dominating sets in cycles, which completes the results of Bertrand et al. [N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and locating–dominating codes on chains and cycles, European Journal of Combinatorics 25 (2004) 969–987]. ► We provide results for a remaining open case in cycles for r -identifying codes. ► We provide complete results in paths for r -identifying codes. ► We give complete results for 2-locating-dominating sets in cycles.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2011.06.008