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

Rennan Dantas 1 Frédéric Havet 2 Rudini Sampaio 1
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : Soit $\mathcal{G}_T$ la grille triangulaire infinie. Pour pout entier strictement positif $k$, nous notons $T_k$ le sous-graphe de $\mathcal{G}_T$ induit par l'ensemble des sommets $\{(x,y)\in\mathbb{Z}\times[k]\}$. Un ensemble $C\subset V(G)$ est un {\it code identifiant} d'un graphe $G$ si pour tout $v\in V(G)$, $N[v]\cap C\neq \emptyset$, et pour tout $u,v\in V(G)$, $N[u]\cap C\neq N[v]\cap C$, o\`u $N[x]$ est le voisinage ferm\'e de $x$ dans $G$. La densit\'e minimum d'un code identifiant de $G$ est not\'ee $d^*(G)$. Dans ce rapport, nous montrons que $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$ et $d^*(T_k)=1/4+1/(4k)$ pour tout $k\geq 7$ impair. De plus, nous montrons que $1/4+1/(4k)\leq d^*(T_k)\leq 1/4+1/(2k)$ pour tout $k\geq 8$ pair.
Type de document :
Rapport
[Research Report] RR-8951, INRIA Sophia Antipolis - I3S. 2016
Liste complète des métadonnées

https://hal.inria.fr/hal-01358064
Contributeur : Frederic Havet <>
Soumis le : mardi 30 août 2016 - 22:26:54
Dernière modification le : vendredi 16 septembre 2016 - 15:20:33

Fichier

RR-8951.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01358064, version 1

Collections

Citation

Rennan Dantas, Frédéric Havet, Rudini Sampaio. Identifying codes for infinite triangular grids with a finite number of rows. [Research Report] RR-8951, INRIA Sophia Antipolis - I3S. 2016. <hal-01358064>

Partager

Métriques

Consultations de
la notice

270

Téléchargements du document

34