Minimum density of identifying codes of king grids

Rennan Dantas 1 Frédéric Havet 2 Rudini Sampaio 1
2 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 : 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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2018, 341 (10), pp.2708 - 2719. 〈10.1016/j.disc.2018.06.035〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01861913
Contributeur : Frederic Havet <>
Soumis le : vendredi 21 décembre 2018 - 08:57:59
Dernière modification le : vendredi 21 décembre 2018 - 09:54:19

Fichier

idcodes-king.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

166

Téléchargements de fichiers

43