2012/07/19 by M. Ghebleh, Ghebleh, M., Ľudovít Niepel +2
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #cs.DM #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1207.4660
arxiv created 2012/07/19 · openalex publication_date 2012/07/19 · arxiv updated 2012/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set S of vertices of a graph G is a dominating set of G if every vertex u of G is either in S or it has a neighbour in S. In other words, S is dominating if the sets S∩ N[u] where u ∈ V(G) and N[u] denotes the closed neighbourhood of u in G, are all nonempty. A set S ⊆ V(G) is called a locating code in G, if the sets S ∩ N[u] where u ∈ V(G) ∖ S are all nonempty and distinct. A set S ⊆ V(G) is called an identifying code in G, if the sets S∩ N[u] where u∈ V(G) are all nonempty and distinct. We study locating and identifying codes in the circulant networks Cn(1,3). For an integer n>6, the graph Cn(1,3) has vertex set Zn and edges xy where x,y ∈ Zn and |x-y| ∈ 1,3. We prove that a smallest locating code in Cn(1,3) has size \lceil n/3 \rceil + c, where c ∈ 0,1, and a smallest identifying code in Cn(1,3) has size \lceil 4n/11 \rceil + c', where c' ∈ 0,1.