Minimum density of identifying codes of king grids

Rennan Dantas 1 Rudini Sampaio 2 Frédéric Havet 3
3 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , 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 product of two paths. We show that for every king grid G, d * (G) ≥ 2/9. In addition, we show this bound is attained only for king grids which are strong products of two infinite paths. Given k ≥ 3, we denote by K k the (infinite) king strip with k rows. We prove that d * (K 3) = 1/3, d * (K 4) = 5/16, d * (K 5) = 4/15 and d * (K 6) = 5/18. 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
Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.51 - 56. 〈10.1016/j.endm.2017.10.010〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01634305
Contributeur : Frederic Havet <>
Soumis le : lundi 13 novembre 2017 - 22:41:00
Dernière modification le : mercredi 15 novembre 2017 - 01:15:47

Fichier

LAGOS-king-code (1).pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Rennan Dantas, Rudini Sampaio, Frédéric Havet. Minimum density of identifying codes of king grids. Electronic Notes in Discrete Mathematics, Elsevier, 2017, 62, pp.51 - 56. 〈10.1016/j.endm.2017.10.010〉. 〈hal-01634305〉

Partager

Métriques

Consultations de la notice

13

Téléchargements de fichiers

3