Solving Two Conjectures regarding Codes for Location in Circulant Graphs

MaRDI QIDQ4611776zbMATH OpenFDO

Authors Ville Junnila, Tero Laihonen, Gabrielle Paris

Publication date 21 January 2019

Full work available at URL https://arxiv.org/abs/1710.00605, https://dmtcs.episciences.org/5049/pdf

zbMATH Keywords

circulant graphidentifying codelocating-dominating code

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Identifying and locating-dominating codes have been widely studied in circulant graphs of type $C_n(1,2,ldots,r)$, which can also be viewed as power graphs of cycles. Recently, Ghebleh and Niepel (2013) considered identification and location-domination in the circulant graphs $C_n(1,3)$. They showed that the smallest cardinality of a locating-dominating code in $C_n(1,3)$ is at least $lceiln/3ceil$ and at most $lceiln/3ceil+1$ for all $ngeq9$. Moreover, they proved that the lower bound is strict when $nequiv0,1,4pmod6$ and conjectured that the lower bound can be increased 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 $lceil4n/11ceil$ and at most $lceil4n/11ceil+1$ for all $ngeq11$. Furthermore, they proved that the lower bound is attained for most of the lengths $n$ and conjectured that in the rest of the cases the lower bound can improved by one. This conjecture is also proved in the 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 to identification and location-domination, also manages to take advantage of the global properties of the codes and the underlying graphs.

Recommendations

• Optimal bounds on codes for location in circulant graphs
• Locating and identifying codes in circulant graphs
• Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
• Identifying codes and locating-dominating sets on paths and cycles
• Locating-dominating codes in cycles
• Locating and identifying codes in dihedral graphs
• Perfect codes in circulant graphs
• Possible cardinalities for locating-dominating codes in graphs
• Codes associated with circulant graphs and permutation decoding
• Identifying and locating-dominating codes on chains and cycles

Cited in

(6)

• On a conjecture regarding identification in Hamming graphs
• Locating and identifying codes in circulant graphs
• Optimal bounds on codes for location in circulant graphs
• Locating and identifying codes in circulant networks
• Locating-dominating codes in cycles
• Exact values for three domination-like problems in circular and infinite grid graphs of small height

This page was built for publication: Solving Two Conjectures regarding Codes for Location in Circulant Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4611776)