Ville Junnila ; Tero Laihonen ; Gabrielle Paris - Solving Two Conjectures regarding Codes for Location in Circulant Graphs

dmtcs:3973 - Discrete Mathematics & Theoretical Computer Science, January 8, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-2
Solving Two Conjectures regarding Codes for Location in Circulant GraphsArticle

Authors: Ville Junnila ; Tero Laihonen ORCID; Gabrielle Paris

    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 $\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 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 $\lceil 4n/11 \rceil$ and at most $\lceil 4n/11 \rceil + 1$ for all $n \geq 11$. 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.


    Volume: Vol. 21 no. 3
    Section: Graph Theory
    Published on: January 8, 2019
    Accepted on: December 17, 2018
    Submitted on: October 3, 2017
    Keywords: Mathematics - Combinatorics
    Funding:
      Source : OpenAIRE Graph
    • Games and graphs; Funder: French National Research Agency (ANR); Code: ANR-14-CE25-0006

    Consultation statistics

    This page has been seen 859 times.
    This article's PDF has been downloaded 274 times.