Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Let $\mathcal{G}_T$ be the infinite triangular grid. For any positive integer $k$, we denote by $T_k$ the subgraph of $\mathcal{G}_T$ induced by the vertex set $\{(x,y)\in\mathbb{Z}\times[k]\}$. A set $C\subset V(G)$ is an {\it identifying code} in a graph $G$ if for all $v\in V(G)$, $N[v]\cap C\neq \emptyset$, and for all $u,v\in V(G)$, $N[u]\cap C\neq N[v]\cap 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\geq 7$ odd. Moreover, we prove that $1/4+1/(4k)\leq d^*(T_k)\leq 1/4+1/(2k)$ for every $k\geq 8$ even.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Tuesday, August 30, 2016 - 10:26:54 PM
Last modification on : Wednesday, October 26, 2022 - 8:14:19 AM


Files produced by the author(s)


  • HAL Id : hal-01358064, version 1



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⟩



Record views


Files downloads