Refereed journal article or data article (A1)
Optimal bounds on codes for location in circulant graphs
List of Authors: Ville Junnila, Tero Laihonen, Gabrielle Paris
Publisher: SPRINGER
Publication year: 2019
Journal: Cryptography and Communications
Journal acronym: CRYPTOGR COMMUN
Volume number: 11
Issue number: 4
Start page: 621
End page: 640
Number of pages: 20
ISSN: 1936-2447
eISSN: 1936-2455
DOI: http://dx.doi.org/10.1007/s12095-018-0316-3
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/41355929
Abstract
Identifying and locating-dominating codes have been studied widely in circulant graphs of type Cn(1,2,3,...,r) over the recent years. In 2013, Ghebleh and Niepel studied locating-dominating and identifying codes in the circulant graphs Cn(1,d) for d=3 and proposed as an open question the case of d>3. In this paper we study identifying, locating-dominating and self-identifying codes in the graphs Cn(1,d), Cn(1,d-1,d) and Cn(1,d-1,d,d+1). We give a new method to study lower bounds for these three codes in the circulant graphs using suitable grids. Moreover, we show that these bounds are attained for infinitely many parameters n and d. In addition, new approaches are provided which give the exact values for the optimal self-identifying codes in Cn(1,3) and Cn(1,4).
Identifying and locating-dominating codes have been studied widely in circulant graphs of type Cn(1,2,3,...,r) over the recent years. In 2013, Ghebleh and Niepel studied locating-dominating and identifying codes in the circulant graphs Cn(1,d) for d=3 and proposed as an open question the case of d>3. In this paper we study identifying, locating-dominating and self-identifying codes in the graphs Cn(1,d), Cn(1,d-1,d) and Cn(1,d-1,d,d+1). We give a new method to study lower bounds for these three codes in the circulant graphs using suitable grids. Moreover, we show that these bounds are attained for infinitely many parameters n and d. In addition, new approaches are provided which give the exact values for the optimal self-identifying codes in Cn(1,3) and Cn(1,4).
Downloadable publication This is an electronic reprint of the original article. |