Identifying codes for infinite triangular grids with a finite number of rows

Rennan Dantas 1 Frédéric Havet 2, 3 Rudini Sampaio 4
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Let G T be the infinite triangular grid. For any positive integer k, we denote by T k the subgraph of G T induced by the vertex set {(x, y) ∈ Z × [k]}. A set C ⊂ V (G) is an identifying code in a graph G if for all v ∈ V (G), N [v] ∩ C = ∅, and for all u, v ∈ V (G), N [u]∩C = N [v]∩C, where N [x] denotes the closed neighborhood of x in G. The minimum density of an identifying code in G is denoted by d * (G). In this paper, we prove that d * (T 1) = d * (T 2) = 1/2, d * (T 3) = d * (T 4) = 1/3, d * (T 5) = 3/10, d * (T 6) = 1/3 and d * (T k) = 1/4 + 1/(4k) for every k ≥ 7 odd. Moreover, we prove that 1/4 + 1/(4k) ≤ d * (T k) ≤ 1/4 + 1/(2k) for every k ≥ 8 even.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01527023
Contributor : Frederic Havet <>
Submitted on : Tuesday, May 23, 2017 - 6:09:17 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Friday, August 25, 2017 - 12:41:44 AM

File

tri-rudini.pdf
Files produced by the author(s)

Identifiers

Citation

Rennan Dantas, Frédéric Havet, Rudini Sampaio. Identifying codes for infinite triangular grids with a finite number of rows. Discrete Mathematics, Elsevier, 2017, 340, pp.1584 - 1597. ⟨10.1016/j.disc.2017.02.015⟩. ⟨hal-01527023⟩

Share

Metrics

Record views

382

Files downloads

51