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
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01358064
Contributor : Frederic Havet <>
Submitted on : Tuesday, August 30, 2016 - 10:26:54 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM

File

RR-8951.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01358064, version 1

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⟩

Share

Metrics

Record views

478

Files downloads

104