Identifying codes for infinite triangular grids with a finite number of rows - Archive ouverte HAL Access content directly
Journal Articles Discrete Mathematics Year : 2017

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

(1) , (2, 3) , (4)
1
2
3
4

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.
Fichier principal
Vignette du fichier
tri-rudini.pdf (307.59 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01527023 , version 1 (23-05-2017)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More