# Locating and Identifying Codes in Circulant Graphs

Authors: Shu Jiao Song; Weiqian Zhang; Can Xu
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

Identifying and locating-dominating codes have been studied widely in circulant graphs. Recently, Ville Junnila et al. (Optimal bounds on codes for location in circulant graphs,Cryptography and Communications; 2019) studied identifying and locating-dominating codes in circulants Cn1,d, Cn1,d−1,d, and Cn1,d−1,d,d+1. In this paper, identifying, locating, and self-identifying codes in the circulant graphs Cnk,d, Cnk,d−k,d, and Cnk,d−k,d,d+k are studied, and this extends Junnila et al.’s results to general cases.


---

## Body

## 1. Introduction

LetΓ=V,E be a graph with vertex set V and edge set E. We say vertices u and v are adjacent, if there is an edge between uandv in Γ. The distancedu,v is the number of edges of a shortest path between the vertices u and v, and it is denoted by du,v. For any vertex u∈V, the open neighborhood of u in Γ is denoted by NΓu=v∈V|du,v=1. The closed neighborhood of u∈V in Γ is denoted by NΓu=NΓu∪u.Given a groupG and a subset S of G, the graph Γ=CayG,S is a Cayley graph on G with respect to S. The vertices in Γ are the elements of G and vertices x and y are adjacent if and only if yx−1∈S. It is known that CayG,S is connected if and only if S generates G. If G is a cyclic group, then Γ is called a circulant graph. We denote Cayℤn,S, S=d1,d2,…,dk, by Cnd1,d2,…,dk, where n and di are positive integers such that di≤n/2 for all i=1,2,…,k. The vertex set of the circulant graph is V=ℤn=0,1,2,…,n−1, and the open neighborhood of arbitrary vertex u∈V is Nu=u−d1,u−d2,…,u−dk∪u+d1,u+d2,…,u+dk.A nonempty subset of verticesC⊆V is called code and its elements are called codewords, and the number of elements in it is called the order of C denoted by C. For a finite nonempty set S⊆V in a graph Γ=V,E, we define the density of a code C⊆V in S by S∩C/S. A code C is called dominating if every vertex u of Γ is either in C or it has a neighbor in C. The I-set of a vertex u depending on a code C is defined by(1)IG,C;u=Nu∩C.A setC⊆VΓ is called a locating code in Γ, if C is a dominating code and for any distinct vertices u,v∈V,C, we have IC;u≠IC;v. In a finite graph Γ, the smallest possible order of a locating code is denoted by γLDΓ. A locating-dominating code with order γLDΓ is called optimal. A set C⊆VΓ is called an identifying code in Γ, if C is a dominating code and for any distinct vertices u,v∈V, we have IC;u≠IC;v. The smallest possible order of an identifying code in a finite graph Γ is denoted by γIDΓ. An identifying code with γIDΓ codewords is called optimal. A code C⊆V is self-identifying in Γ=V,E if for all distinct u,v∈V, IC;u,IC;v≠∅. In addition, there is an equivalent definition of self-identifying code [1, 2]: C is a self-identifying code in Γ if and only if for all u∈V, we have IC;u≠∅ and ∩c∈IC;uNc=u. In a finite graph Γ, the smallest possible order of a self-identifying code is denoted by γSIDΓ and a self-identifying code with order γSIDΓ is called optimal.By definition, it is easy to see every identifying code is also a locating code and a self-identifying code is also an identifying code.In 1988, to promote nuclear power plant safety, locating codes were first introduced by P. J. Slater [3]; vertices of a locating-dominating set S correspond to safeguards and an intruder corresponding to a vertex in V,S. In 1998, identifying codes were first introduced in a more general form by Karpovsky et al. [4].Locating and identifying codes of some special graphs have been studied (see [5–10] for reference). Great efforts are made in studying locating and identifying codes in circulants. M. Ghebleh and L. Niepel studied locating and identifying code numbers of Cn1,3 in [11], but they stated as an open question what happens in the graphs Cn1,d with d being greater than 3 and mentioned that the methods used in their paper seem to be nonapplicable. So, Ville Junnila, Tero Laihonen, and Gabrielle Paris present a new approach to study identifying, locating-dominating, and self-identifying codes in the circulant graphs Cn1,d, Cn1,d−1,d, and Cn1,d−1,d,d+1 using suitable grids in [12]. However, there is no relevant conclusion for the more general 4,6,8 degree circulant graphs. This is the motivation of this paper.Theorem 1.
Letn, k, anddbe positive integers such thatn>2d>2k≥2,k,d,n=1, andΓ=Cnk,d. Then,Γis connected and(2)γIDΓ≥7n20,γLDΓ≥3n10,γSIDΓ≥n2.Theorem 2.
Letn, k, anddbe positive integers such thatn>2d>4k,k,d,n=1, andΓ=Cnk,d−k,d. Then,Γis connected and(3)γIDΓ≥n4,γSIDΓ≥n2.Theorem 3.
Letn, k, anddbe positive integers such thatn>2d>4k,2d+k≠n,2d+2k≠n,k,d,n=1, andΓ=Cnk,d−k,d,d+k. Then,Γis connected and(4)γLDΓ≥n5,γIDΓ≥2n9,γSIDΓ≥n3.Remark 1.
(i)
There is an infinite sequence of identifying codes in the circulant graphsCnk,d−k,d such that their density tends to 1/4.(ii)
We have an infinite sequence of identifying codes in the circulant graphsCnk,d−k,d,d+k such that their density tends to 2/9.(iii)
All other bounds given above are optimal. Examples are given in this paper.


## 2. Infinite Grids and Circulant Graphs

In order to study the codes of circulant graphs, we first give the necessary and sufficient conditions of these circulants to be connected.Lemma 1.
Letnanddbe positive integers andd≥2. Then,Cnk,d,Cnk,d−k,d,andCnk,d−k,d,d+kare connected if and only ifk,d,n=1.Proof.
Letd,n=d1 and k,n=k1. Then, there exist x,y∈ℤ such that dx=d1modnand ky=k1modn. If k,d,n=1, then d1,k1,n=1. Hence, there exist t,m∈ℤ such that d1t+k1m=s1modn, where s1,n=1. So, there exists t0∈ℤ such that s1t0=1modn, and then we have d1tt0+k1mt0=1modn and dxtt0+kymt0=1modn. So, da+kb=1modn, where xtt0=a and ymt0=b. Thus, k,d=ℤn, Cnk,d, Cnk,d−k,d, and Cnk,d−k,d,d+k are connected.
On the contrary, ifk,d,n=l>1, we have k,d=l<ℤn, and Cnk,d is not connected. In addition, k,d−k,d=k,d−k,d,d+k=k,d.Next, we give definitions of infinite square, triangular, and king grids.(i)
The square gridS: the vertex set of the square grid is V=ℤ2, and vertex u=x,y∈ℤ2 is adjacent to v if and only if v∈x±1,y,x,y±1=NS;u (see Figure 1(a) for details).(ii)
The triangular gridT: the vertex set of the triangular grid is V=ℤ2, and vertex u=x,y∈ℤ2 is adjacent to v if and only if v∈NS;u∪x+1,y+1,x−1,y−1=NT;u (see Figure 1(b) for details).(iii)
The king gridK: the vertex set of the king grid is V=ℤ2, and vertex u=x,y∈ℤ2 is adjacent to v if and only if v∈NT;u∪x+1,y−1,x−1,y+1=NK;u (see Figure 2 for details).Figure 1
(a) The close neighborhood ofu in the square grid S, and u=x,y∈ℤ2 is denoted by a round black spot. Its open neighborhood is the set of all the hollow dots. (b) The close neighborhood of u in the triangular grid T, and u=x,y∈ℤ2 is denoted by a black spot. Its open neighborhood is the set of all the hollow dots.
(a)(b)Figure 2
The close neighborhood ofu in the king grid S, and u=x,y∈ℤ2 is denoted by a black spot. Its open neighborhood is the set of all the hollow dots.In order to study the codes of circulant graphs, we give correspondences between circulant graphs and grids.(i)
LetΓ=Cnk,d be a circulant graph. Let φ1 be the mapping from the vertices in the square grid to vertices in Γ, such that(5)φ1:x=i,j⟼i⋅k+j⋅dmodn.(ii)
LetΓ=Cnk,d−k,d be a circulant graph. Let φ2 be the mapping from the vertices in the triangular grid to vertices in Γ, such that(6)φ2:x=i,j⟼i⋅k+j⋅d−kmodn.(iii)
LetΓ=Cnk,d−k,d,d+k be a circulant graph. Let φ3 be the mapping from the vertices in the square grid to vertices in Γ, such that(7)φ3:x=i,j⟼i⋅k+j⋅dmodn.Now, we will prove that these maps keep the adjacency relationships.(i)
By the definition ofφ1, vertex i,j in the square grid S corresponds to the vertex i⋅k+j⋅dmodn in Cnk,d, then(8)i,jis adjacent toi,j+1i,j−1i+1,ji−1,j⟺i⋅k+j⋅dis adjacent toi⋅k+j+1⋅d,i⋅k+j−1⋅d,i+1⋅k+j⋅d,i−1⋅k+j⋅d.Therefore, the map keeps the adjacency relationships.(ii)
By the definition ofφ2, vertex i,j in the triangular grid T corresponds to the vertex i⋅k+j⋅d−kmodn in Cnk,d−k,d, then(9)i,jis adjacent toi,j+1i,j−1i+1,ji−1,ji+1,j+1i−1,j−1⟺i⋅k+j⋅d−kis adjacent toi⋅k+j+1⋅d−k,i⋅k+j−1⋅d−k,i+1⋅k+j⋅d−k,i−1⋅k+j⋅d−k,i+1⋅k+j+1⋅d−k,i−1⋅k+j−1⋅d−k.Therefore, the map keeps the adjacency relationships.(iii)
By the definition ofφ3, vertex i,j in the king grid K corresponds to the vertex i⋅k+j⋅dmodn in Cnk,d−k,d,d+k, then(10)i,jis adjacent toi,j+1i,j−1i+1,ji−1,ji+1,j+1i−1,j−1i−1,j+1i+1,j−1⟺i⋅k+j⋅dis adjacent toi⋅k+j+1⋅d,i⋅k+j−1⋅d,i+1⋅k+j⋅d,i−1⋅k+j⋅d,i+1⋅k+j+1⋅d,i−1⋅k+j−1⋅d,i−1⋅k+j+1⋅d,i+1⋅k+j−1⋅d.Therefore, the map keeps the adjacency relationships.Next, we give the relationship about identifying, locating-dominating, and self-identifying code between the circulantsCnk,d, Cnk,d−k,d, and Cnk,d−k,d,d+k and the square, triangular, and king grids.Lemma 2.
Letn,d,k, andtbe positive integers such thatn>2d>2k≥2. IfCis an identifying code inCnk,dwith ordert, then there is an identifying code in the infinite square gridSwith the densityt/n. Analogous conclusions remain true for locating and self-identifying codes.Proof.
LetΓ=Cnk,d be a circulant graph, and C an identifying code in Γ. Let CS=i,j∈ℤ2|i⋅k+j⋅d∈C be a code in S.
First, we show thatCS is an identifying code in the square grid S. Suppose there are two distinct vertices x=i,j∈ℤ2 and y=i,j+a,b∈ℤ2a,b∈ℤ in the square grid such that IS;x=IS;y. Because C is a dominating set, so is CS, and then IS;x and IS;y are nonempty sets. So, we just need to consider the cases of dSx,y≤2 (if dSx,y≥3, then Nx∩Ny=∅, Nx≠Ny). Without less of generality, we assume b≥0 (otherwise, you just need to switch the roles of x and y). So, a,b∈S=1,0,−1,0,0,1,1,1,−1,1,2,0,−2,0,0,2. Because IS;x=IS;y, we have IΓ;i⋅k+j⋅d=IΓ;i+a⋅k+j+b⋅d. Moreover, because C is an identifying code, we have i⋅k+j⋅d≡i+a⋅k+j+b⋅d (mod n). Hence, a⋅k+b⋅d≡0 (mod n). However, a,b∈S, IS;x≠IS;y by verifying all cases of a,b which contradicts to IS;x=IS;y, so CS is an identifying code in S.
The proof is similar for the locating codes. Just notice that the verticesx=i,j∈ℤ2 and y=x+a,b∈ℤ2 are non-codewords, and their corresponding vertices i⋅k+j⋅d and i+a⋅k+j+b⋅d are also non-codewords in Γ.
Now, we give the proof for self-identifying codes. By the definitions of identifying and self-identifying codes, we know every self-identifying code is also an identifying code. Suppose thatC is a self-identifying code in Γ, C is also an identifying code in it. According to the above proof of identifying codes, we know CS is an identifying code in S. Next, we show that IS;x,IS;y≠∅ for any distinct vertices x=i,j∈ℤ2 and y=x+p,q∈ℤ2p,q∈ℤ. Since CS is an identifying code, the result is true if dSx,y≥3.
Suppose that1≤dSx,y≤2, namely, p,q∈−1,−1,0,−2,1,−1,2,0,1,1,0,2,−1,1,−2,0,−1,0,1,0,0,1,0,−1. Hence, the set IΓ;i⋅k+j⋅d,IΓ;i+p⋅k+j+q⋅d contains a codeword of C because C is a self-identifying code in Γ. Notice that i⋅k+j⋅d and i+p⋅k+j+q⋅d are distinct vertices by verifying all of the above p,q cases in Γ as n>2d>2k. Thus, IS;x,IS;y always contains a codeword of CS. This completes the proof.Lemma 3.
Letn,d,k, andtbe positive integers such thatn>2d>4k. IfCis an identifyinglocatingorself−identifyingcode inCnk,d−k,dwith ordert, then there is an identifyinglocating or self−identifyingcode in the infinite triangular gridTwith the densityt/n.Proof.
LetΓ=Cnk,d−k,d be a circulant graph and C an identifying code in Γ. Let CT=i,j∈ℤ2|i⋅k+j⋅d−k∈C be a code in T.
Now, we claim thatCT is an identifying code in the triangular grid T. Suppose that CT is not an identifying code, so there are two distinct vertices x=i,j∈ℤ2 and y=x+a,b∈ℤ2a,b∈ℤ such that IT,x=IT,y in the triangular grid T.
BecauseC is a dominating set, so is CT, and then IT;x and IT;y are nonempty sets. So, we just need to consider the cases of dTx,y≤2 (if dTx,y≥3, then Nx∩Ny=∅, Nx≠Ny). Without less of generality, we assume b≥0 (otherwise, you just need to switch the roles of x and y). So, a,b∈T=1,0,−1,0,1,1,−1,1,2,0,−2,0,0,2,2,1,1,2,2,2,0,1. Because IT;x=IT;y, we have IΓ;i⋅k+j⋅d−k=IΓ;i+a⋅k+j+b⋅d−k. Moreover, because C is an identifying code, we have i⋅k+j⋅d−k≡i+a⋅k+j+b⋅d−kmodn. Hence, a⋅k+b⋅d−b⋅k≡0modn. However, a,b∈T, IT,x≠IT,y by verifying all cases of a,b which contradicts to IT;x=IT;y, so CT is an identifying code in T.
The proof is similar for the locating-dominating codes. Just notice that the verticesx=i,j∈ℤ2 and y=x+a,b∈ℤ2 are non-codewords in T, and their corresponding vertices i⋅k+j⋅d−k and i+a⋅k+j+b⋅d−k are also non-codewords in Γ.
Now, we give the proof for self-identifying codes. Suppose thatC is a self-identifying code in Γ (it is also an identifying code) and CT is an identifying code in T. Next, we show that IT;x,IT;y≠∅ for any distinct vertices x=i,j∈ℤ2 and y=x+p,q∈ℤ2p,q∈ℤ. Since CT is an identifying code, the result is true if dTx,y≥3.
Suppose that1≤dTx,y≤2, namely, p,q∈−2,−1,−2,−2,−1,−2,0,−2,1,−1,2,0,2,1,2,2,1,2,0,2,−1,1,−2,0,−1,0,−1,−1,0,−1,1,0,1,1,0,1.
Hence, the setIΓ;i⋅k+j⋅d−k,IΓ;i+p⋅k+j+q⋅d−k contains a codeword of C because C is a self-identifying code in Γ. Notice that i⋅k+j⋅d−k and i+p⋅k+j+q⋅d−k are distinct vertices by verifying all of the above p,q cases in Γ as n>2d>4k. Thus, IT;x,IT;y always contains a codeword of CT. We are done.Lemma 4.
Letn,d,k, andtbe positive integers such thatn>2d>4k,2d+k≠n, and2d+2k≠n. IfCis an identifying code inCnk,d−k,d,d+kwith ordert, then there is an identifying code in the infinite king gridKwith the densityt/n. Analogous conclusions remain true for locating and self-identifying codes.Proof.
LetΓ=Cnk,d−k,d,d+k be a circulant graph and C an identifying code in Γ. Let CK=i,j∈ℤ2|i⋅k+j⋅d∈C be a code in K.
We first show thatCK is an identifying code in the king grid K. Suppose there are two distinct vertices x=i,j∈ℤ2 and y=i,j+a,b∈ℤ2a,b∈ℤ in the king grid such that IK;x=IK;y. Because C is a dominating set, so is CK, and then IK;x and IK;y are nonempty sets. So, we just need to consider the cases of dKx,y≤2 (if dKx,y≥3, then Nx∩Ny=∅ and Nx≠Ny). Without loss of generality, we assume b≥0 (otherwise, you just need to switch the roles of x and y). So, a,b∈K=0,1,1,0,1,1,−1,1,−1,0,0,2,2,0,−2,0,1,2,−1,2,2,2,−2,2,2,1,−2,1. Because IS;x=IS;y, we have IΓ;i⋅k+j⋅d=IΓ;i+a⋅k+j+b⋅d. Moreover, because C is an identifying code, we have i⋅k+j⋅d≡i+a⋅k+j+b⋅dmodn. Hence, a⋅k+b⋅d≡0modn. However, a,b∈K, IK,x≠IK,y by verifying all cases of a,b which contradicts to IK;x=IK;y, so CK is an identifying code in K.
The proof is similar for the locating codes. Just notice that the verticesx=i,j∈ℤ2 and y=x+a,b∈ℤ2 are non-codewords in K, and their corresponding vertices i⋅k+j⋅d and i+a⋅k+j+b⋅d are also non-codewords in Γ.
Now, we give the proof for self-identifying codes. Suppose thatC is a self-identifying code in Γ (it is also an identifying code) and CK is an identifying code in K. Next, we show that IK;x,IK;y≠∅ for any distinct vertices x=i,j∈ℤ2 and y=x+p,q∈ℤ2p,q∈ℤ. Since CK is an identifying code, the result is true if dKx,y≥3.
Suppose that1≤dKx,y≤2, namely, p,q∈−2,2,−2,1,−2,0,−2,−1,−2,−2,−1,−2,0,−2,1,−2,2,−2,2,−1,2,0,2,1,2,2,1,2,0,2,−1,2,−1,−1,0,−1,1,−1,1,0,1,1,0,1,−1,1,−1,0. Hence, the set IΓ;i⋅k+j⋅d,IΓ;i+p⋅k+j+q⋅d contains a codeword of C because C is a self-identifying code in Γ. Notice that i⋅k+j⋅d and i+p⋅k+j+q⋅d are distinct vertices by verifying all of the above p,q cases in Γ as n>2d>4k, 2d+k≠n, and 2d+2k≠n. Thus, IK;x,IK;y always contains a codeword of CK. This completes the proof.Proof.
of Theorems 1, 2, and 3. According to Table1 and Lemmas 2, 3, and 4, the three theorems hold.Table 1
The densities of optimal identifying, locating-dominating, and self-identifying inS, T, and K.
Square gridSTriangular gridTKing gridKLD3/10 [13]1/5 [8]ID7/20 [14, 15]1/4 [4]2/9 [16, 17]Self-ID1/2 [18]1/2 [18]1/3 [18]


## 3. The Constructions for Lower Bounds

In this section, we will give codes in the circulant graphs of meeting or infinitely approaching the lower bounds. The following lemma gives optimal ID codes and LD codes inCnk,d.Theorem 4.
LetCnk,dbe a circulant graph withk,d,andnbeing positive integers such thatn>2d>2k≥2andk,d,n=1.(i)
Ifn≡0mod20, k≡2mod20, and d≡3mod20, thenγIDCnk,d=7n/20.(ii)
Ifn≡0mod20, k≡3mod20, and d≡5mod20, thenγLDCnk,d=3n/10.Proof.
Case 1: letn≡0mod20, k≡2mod20, and d≡3mod20. We define B1=0,4,6,7,13,14,16 and(11)C1=u∈ℤn|u≡bmod20forb∈B1.It is easy to verify thatB1 is an identifying code in C202,3, where 2,3,20=1. Next, if we prove that all the I-sets ICnk,d,C1;x are nonempty and unique, then C1 is an identifying code in Cnk,d. According to the structure of C1, it is easy to know that(12)IC202,3,B1;x0≡ICnk,d,C1;xmod20,wherex≡x0mod20 is an integer and 0≤x0≤19. Hence, ICnk,d,C1;x are nonempty for all x∈ℤn. Next, suppose x∈ℤn and y∈ℤn are distinct vertices, and the following two cases are discussed:Case 1.1:x≠ymod20: let x′ and y′ be integers such that x=x′mod20, y=y′mod20, 0≤x′≤19, and 0≤y′≤19. Hence, if ICnk,d,C1;x=ICnk,d,C1;y, then IC202,3,B1;x′=IC202,3,B1;y′. This contradicts the fact that B1 is the identifying code in C202,3.Case 1.2:x≡ymod20: Next, we show that NCnk,d,C1;x∩NCnk,d,C1;y=∅.Assume that there arex,y∈Zn such that x+h=y+h′∈NCnk,d,C1;x∩NCnk,d,C1;y for some h,h′∈−d,−k,0,k,d. We have y+h′−x−h=0mod20, and then h=h′mod20 due to x≡ymod20. So, h=h′ and x=y (recalled n>2d>2k). It is a contradiction. So, any vertex of ℤn is dominated by a codeword of C1 and ICnk,d,C1;x≠ICnk,d,C1;y. Thus, C1 is an identifying code in Cnk,d.Case 2: letn≡0mod20,k≡3mod20, and d≡5mod20. We define B2=0,1,2,11,12,13 and(13)C2=u∈ℤn|u≡bmod20forb∈B2.
It is easy to verify thatB2 is an identifying code in C203,5, where 3,5,20=1. Then, it is similar as in case 1 that C2 is an identifying code in Cnk,d, where k,d,n=1 (just notice x and y are assumed to be non-codewords).In the next theorem, we give an infinite sequence of identifying codes which infinitely approach the lower bound for identifying codes in Theorem2.Theorem 5.
LetCnk,d−k,dbe a circulant graph withk,d,npositive integers andn>2d>4k,k,d,n=1. Then, there is an infinite sequence of identifying codes in the circulant graphsCnk,d−k,dsuch that their density tends to1/4.Proof.
Letk>1 be even, d=3k−1 be odd, and n=6k. Let S=j|0≤j≤k,j≡0mod2. Define(14)Cd=v∈ℤn|v≡bmod2kfor someb∈S.
It is easy to see that codeCd has order 3k/2+1. Therefore, limk⟶∞Cd/n=1/4.
Next, we will prove thatCd is an identifying code in Cnk,d−k,d.Case 1: ifk≤s≤2k−1 and x≡smod2k is odd, we can obtain x−d,x+d⊆Ix. Because Nx+d∩Nx−d=x, we know only Ix contains elements x+dandx−d at the same time. So, Ix≠Iy for any x≠y. If k≤s≤2k−1 or s=0 and x≡smod2k is even, then we have x−k,x+k⊆Ix. Since Nx+k∩Nx−k=x, Ix≠Iy for any x≠y.Case 2: if1≤s≤k−1 and x≡smod2k is odd, we know x−d+k,x+d−k⊆Ix. Since Nx−d+k∩Nx+d−k=x, we know only Ix contains elements x+d−kandx−d+k at the same time. So, Ix≠Iy for any x≠y. If 1≤s≤k−1 and x≡smod2k is even, then we have Ix=x.
In summary,Cd is an identifying code in Cnk,d−k,d and their density tends to 1/4.Now, we give the construction of optimal locating and identifying codes in the circulant graphCnk,d−k,d,d+k.Theorem 6.
LetCnk,d−k,d,d+kbe a circulant graph withk,d,npositive integers such thatn>2d>4k,2d+k≠n,2d+2k≠n, andk,d,n=1.(i)
Fork=2,d=9,n≥30, andn≡0mod10, thenγLDCn2,7,9,11=n/5.(ii)
We have an infinite sequence of identifying codes in the circulant graphsCnk,d−k,d,d+ksuch that their density tends to2/9.Proof.
(i)
Letk=2, d=9, n≥30, and n≡0mod10. Denote a code(15)C′=v∈ℤn|v≡0mod10orv≡6mod10.Next, we will verifyC′ is a locating code in Cn2,7,9,11.According to the above conditions, we can obtain theI-sets of non-codewordsx of modulo 10.Letx≠y. Next, we just need prove that Ix≠Iy for any non-codewords x and y, and the following two cases are discussed.Case 1:x≠ymod10: according to Table 2, it is easy to see that Ix≠Iy except x≡3mod10 and y≡8mod10. Therefore, we consider this special case. We know that Ix=x−7,x+7 and Iy=y−2,y+2. If Ix=Iy, owing to the data in columns Ix and Ixmod10, we have(16)cx−7≡y−2modn,x+7≡y+2modn.It implies that, for any0≤x,y≤n−1,(17)2x≡2ymodn,y−x=5.Assume thaty>x (otherwise, exchange the roles of x and y), then(18)2x≡2ymodn,y−x=5.So,2x≠2x+10modn when n≥30 (only n=10 equals sign holds). Thus, 2x≠2ymodn if n≥30 and n≡0modn and Ix≠Iy for any x≠ymod10.Case 2:x≡ymod10.: in this case, the codewords in Ix are translated along ℤn to obtain the codewords in Iy, so Ix≠Iy for any x≡ymod10.(ii)
Letk=5, d≥15, d≡3mod6, and n=3d−9n≡0mod6. Next, we divide the vertices of the circulant graph into three parts: A1=0,1,2,…,d−1, A2=d,d+1,d+2,…,2d−1, andA3=0,1,2,…,n−1,A1∪A2. We define the code(19)Cd=v|v∈A1∪A3,v≡5mod6∪v|v∈A2,v≡0,4mod6.
Next, we will add another 7 codewords toCd and get Cd′, so as to construct an identifying code of circulant graph. The value Cd/n tends to 2/9 when d tends to infinity. Firstly, we remove some “borderline” vertices from above three parts and denote A1′=A1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,d−5,d−4,d−3,d−2,d−1, A2′=A2,d,d+1,d+2,d+3,d+4,2d−5,2d−4,2d−3,2d−2,2d−1, and A3′=A3,2d,2d+1,2d+2,2d+3,2d+4,3d−14,3d−13,3d−12,3d−11,3d−10. These borderline vertices are discussed at the end. Let us first check the I-sets Ix for x∈A1′∪A2′∪A3′ (notice that Ix is obtained by relying on Cd).
According to Tables3–5, these I-sets are analyzed and compared. Obviously, when Ix=1, the I-sets are different. Now, consider the case of Ix=2. In Tables 3, 4, and 5, we can see the distances dc1,c2=c1−c2 with c1>c2. If the distance dc1,c2 is different, the I-sets are also different, and if the distance dc1,c2 is same, the c1mod6 and c2mod6 are different as shown in Tables 3–5, so the I-sets cannot be the same. The following is the case of Ix=3. From Tables 3, 4, and 5, we can see that I-sets are different except for x∈A1′, where x≡2mod6 and y∈A3′ (y≡2mod6). However, through verification, we can get dc1,c2=d−4 in Ix, where c1=5mod6,c2=0mod6, and dc1,c2=d−14 in Iy, where c1=5mod6andc2=0mod6. Consequently, Ix≠Iy if x,y∈A1′∪A2′∪A3′ and x≠y.
For the borderline vertices, we have the followingI-sets distinguished: I0=5,2d−14, I1=d−4,d+1,2d−8, I2=d+7,2d−12,2d−2, I3=d+3,2d−6, I5=5, I6=11,d+1,2d−8, I7=d+7,2d−2, I8=d+3,d+13,2d−6, I9=d+9,2d+5, I10=5,d+15, I11=11, I12=17,d+7,2d−2, Id−2=d+3,2d−2,3d−16, I2d−3=11,2d−8, I2d+3=17,d+3,2d−2, I3d−14=d−10,2d−14, I3d−13=d−4,d+1,2d−18,2d−8, I3d−11=d+3,2d−6,3d−16, and I3d−10=3d−10. We verify the I-sets of remaining vertices by considering Ix, Ixmod6, and the distance between codewords: I4=d+9,3d−10=Id+4, I13=d+13=Id+13, Id−5=d−10=Id−10, Id−4=d−4,d+1=Id+1, Id−3=2d−8=I2d−8, Id−1=2d−6,3d−10=Id−6, Id=5,2d+5=Id+5, Id+2=d+7=Id+7, Id+3=d+3,2d−2=I2d−2, I2d−5=d−10,3d−10=I2d−10, I2d−4=5,d−4,d+1=I2d+1, I2d−1=2d−6=I2d−6, I2d=2d+5=I2d+5, I2d+2=11,d+7=I2d+7, I2d+4=d+9=Id+9, and I3d−12=2d−12=I2d−12. We add seven more codewords, namely, D=0,6,9,12,d−7,2d+4,2d+10 to the code Cd to avoid these same I-sets. The new code is denoted by Cd′=Cd∪D. Now let us verify Ix based on Cd′. We know that if ICd,x≠ICd,y, then ICd′,x≠ICd′,y. In addition, 0∈Id−5,Id−10, 0∈I2d−4,I2d+1, 6∈I2d−8,Id−3, 6∈Id+1,Id−4, 6∈I2d+2,I2d+7, 9∈Id+9,I2d+4, 9∈I2d−5,I2d−10, 12∈Id+7,Id+2, d−7∈I2d−12,I3d−12, d−7∈I2d−2,Id+3, 2d+4∈I2d−1,I2d−6, 2d+4∈I13,Id+13, 2d+4∈Id+4,I4, 2d+4∈Id−1,Id−6, 2d+10∈I2d+5,I2d, and 2d+10∈Id+5,Id. Therefore, Cd′ is an identifying code and its density tends to 2/9.Table 2
Ix and Ixmod10.
x (mod 10)I(x)I(x) (mod 10)1{x − 11,x + 9}0,02{x − 2}03{x − 7,x + 7}6,04{x + 2}65{x − 9,x + 11}6,67{x − 7,x − 11,x + 9}0,6,68{x − 2,x + 2}6,09{x − 9,x + 11,x + 7}0,0,6.Table 3
Ix and Ixmod10.
x∈A1′I(x)dc1,c2Ixmod60mod6x+5,x+d−5d−105,41x−d−5,x+dd−145,42x−d,x+d−5,x+d+55,0,43x−d+5,x+dd−45,04x−5,x+d+5d+105,05x5Table 4
Ix and Ixmod10.
x∈A2′Ixdc1,c2Ixmod60mod6x01x−d−5,x+5,x+d−55,0,52x−d,x+dd−95,53x−d+5,x−5,x+d+55,4,54x45x−5,x+5100,4Table 5
Ix and Ixmod10.
x∈A3′Ixdc1,c2Ixmod60mod6x−d−5,x+5d+104,51x−d,x+d−5d−44,52x−d−5,x−d+5,x+d0,4,53x−d,x+d+5d − 140,54x−d+5,x−5d − 100,55x5In the following theorem, we will show that there are infinite families of circulants in which the lower bounds of self-identifying codes in Theorem1, 2, and 3 can be reached.Theorem 7.
Letk,d,andnbe integers such thatd≥4k,d,n=1.(i)
Ifkis odd,dis even,d>k,n≥4d+1, andn≡0mod2, thenγSIDCnk,d=n/2.(ii)
Ifkis odd,d>k,n≥4d+1, andn≡0mod2, thenγSIDCnk,d−k,d=n/2.(iii)
Ifk≡1mod3,d≡1mod3,d>k,n≥4d+4k+1, andn≡0mod3, thenγSIDCnk,d−k,d,d+k=n/3.Proof.
(i)
Let the codeC=v∈ℤn|v≡0mod2, C=n/2. We will show that C is a self-identifying code in Cnk,d. If x≡0mod2, then Ix=x−d,x,x+d. If x≡1mod2, then Ix=x−k,x+k. Because n≥4d+1, we have Nx−d∩Nx+d=x and Nx−k∩Nx+k=x. This meets the definition of a self-identifying code, which is Ix≠∅ and ∩c∈IC;xNc=x. Thus, C is a self-identifying code in Cnk,d and γSIDCnk,d=n/2.(ii)
Let the codeC=v∈ℤn|v≡0mod2, C=n/2. We will prove that C is a self-identifying code in Cnk,d−k,d. Suppose d is even (resp. odd); then, if x≡0mod2, there is x−d,x+d⊆Ix (resp. x−d+k,x+d−k⊆Ix), so ∩c∈IxNc=x, and if x≡1mod2, there is x−d+k,x+d−k⊆Ix (resp. x−d,x+d⊆Ix); hence, again ∩c∈IxNc=x. Therefore, C is a self-identifying code in Cnk,d−k,d and γSIDCnk,d−k,d=n/2.(iii)
LetC=v∈ℤn|v≡0mod3, C=n/3. Next, we will prove that C is a self-identifying code in Cnk,d−k,d,d+k. If x≡0mod3, we can get Ix=x−d+k,x,x+d−k due to k=1mod3 and d=1mod3. If x≡1mod3 (resp. x≡2mod3), then we have Ix=x−d,x−k,x+d+k (resp. Ix=x−d−k,x+k,x+d). Anyhow, the condition ∩c∈IxNc=x is satisfied due to the fact that n≥4d+4k+1. Thus, C is a self-identifying code in Cnk,d−k,d,d+k and γSIDCnk,d−k,d,d+k=n/3.



---

*Source: 4056910-2021-10-28.xml*