Solving Two Conjectures regarding Codes for Location in Circulant Graphs

Identifying and locating-dominating codes have been widely studied incirculant graphs of type $C_n(1,2, \ldots, r)$, which can also be viewed aspower graphs of cycles. Recently, Ghebleh and Niepel (2013) consideredidentification and location-domination in the circulant graphs $C_n(1,3)$. Theyshowed that the smallest cardinality of a locating-dominating code in$C_n(1,3)$ is at least $\lceil n/3 \rceil$ and at most $\lceil n/3 \rceil + 1$for all $n \geq 9$. Moreover, they proved that the lower bound is strict when$n \equiv 0, 1, 4 \pmod{6}$ and conjectured that the lower bound can beincreased by one for other $n$. In this paper, we prove their conjecture.Similarly, they showed that the smallest cardinality of an identifying code in$C_n(1,3)$ is at least $\lceil 4n/11 \rceil$ and at most $\lceil 4n/11 \rceil +1$ for all $n \geq 11$. Furthermore, they proved that the lower bound isattained for most of the lengths $n$ and conjectured that in the rest of thecases the lower bound can improved by one. This conjecture is also proved inthe paper. The proofs of the conjectures are based on a novel approach which,instead of making use of the local properties of the graphs as is usual toidentification and location-domination, also manages to take advantage of theglobal properties of the codes and the underlying graphs