Minimum density of identifying codes of king grids - Archive ouverte HAL Access content directly
Journal Articles Discrete Mathematics Year : 2018

Minimum density of identifying codes of king grids

(1) , (2) , (1)
1
2

Abstract

A set C ⊆ V (G) is an identifying code in a graph G if for all v ∈ V (G), C[v] = ∅, and for all distinct u, v ∈ V (G), C[u] = C[v], where C[v] = N [v] ∩ C and N [v] denotes the closed neighbourhood of v in G. The minimum density of an identifying code in G is denoted by d * (G). In this paper, we study the density of king grids which are strong products of two paths. We show that for every king grid G, d * (G) ≥ 2/9 = 0.222. In addition, we show that this bound is attained only for king grids which are strong products of two infinite paths. Given a positive integer k, we denote by K k the (infinite) king strip with k rows. We prove that d * (K 3) = 1/3 = 0.333, d * (K 4) = 5/16 = 0.3125, d * (K 5) = 0.2666 and d * (K 6) = 5/18 = 0.2777. We also prove that 2 9 + 8 81k ≤ d * (K k) ≤ 2 9 + 4 9k for every k ≥ 7.
Fichier principal
Vignette du fichier
idcodes-king.pdf (315.05 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01861913 , version 1 (21-12-2018)

Identifiers

Cite

Rennan Dantas, Frédéric Havet, Rudini Sampaio. Minimum density of identifying codes of king grids. Discrete Mathematics, 2018, 341 (10), pp.2708 - 2719. ⟨10.1016/j.disc.2018.06.035⟩. ⟨hal-01861913⟩
49 View
101 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More