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

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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2017, 340, pp.1584 - 1597. <10.1016/j.disc.2017.02.015>
Liste complète des métadonnées


https://hal.inria.fr/hal-01527023
Contributeur : Frederic Havet <>
Soumis le : mardi 23 mai 2017 - 18:09:17
Dernière modification le : jeudi 15 juin 2017 - 09:09:29
Document(s) archivé(s) le : vendredi 25 août 2017 - 00:41:44

Fichier

tri-rudini.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

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>

Partager

Métriques

Consultations de
la notice

112

Téléchargements du document

20