FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
December 11, 16:00 ~ 16:30 - Room B11
On Connected Identifying Codes for Infinite Lattices
Victor Campos
ParGO - Universidade Federal do Ceará, Brazil - campos@lia.ufc.br
An identifying code in a graph $G$ is a set $C$ of vertices of $G$ such that the closed neighbourhood of every vertex contains a unique and non-empty subset of $C$. We say that $C$ is a connected identifying code if $G[C]$ is connected. We prove that if a finite graph $G$ on $n$ vertices has maximum degree $\Delta$, then any connected identifying code $C$ satisfies $|C| \ge \frac{2n-2}{\Delta+1}$. We also show this bound is best possible and that the coefficient of $n$ cannot be improved for $\Delta$-regular graphs. We also show that the minimum density of connected identifying codes for the infinite triangular, hexagonal and square lattices are $\frac{1}{3}$, $\frac{1}{2}$ and $\frac{2}{5}$, respectively.
Joint work with Fabrício Benevides (ParGO - Universidade Federal do Ceará), Mitre Dourado (Universidade Federal do Rio de Janeiro), Rudini Sampaio (ParGO - Universidade Federal do Ceará) and Ana Silva (ParGO - Universidade Federal do Ceará).