Identifying codes in graphs of given maximum degree: Characterizing trees

Abstract

An identifying code of a closed-twin-free graph $G$ is a dominating set $S$ of vertices of $G$ such that any two vertices in $G$ have a distinct intersection between their closed neighborhoods and $S$. It was conjectured that there exists an absolute constant $c$ such that for every connected graph $G$ of order $n$ and maximum degree $\hat{I}”$, the graph $G$ admits an identifying code of size at most $(\frac{\hat{I}”-1}{\hat{I}}”)n+c$. We provide significant support for this conjecture by exactly characterizing every tree requiring a positive constant $c$ together with the exact value of the constant. Hence, proving the conjecture for trees. For $\hat{I}”=2$ (the graph is a path or a cycle), it is long known that $c=3/2$ suffices. For trees, for each $\hat{I}”\ge 3$, we show that $c=1/\hat{I}”\le 1/3$ suffices and that $c$ is required to have a positive value only for a finite number of trees. In particular, for $\hat{I}”=3$, there are 12 trees with a positive constant $c$ and, for each $\hat{I}”\ge 4$, the only tree with positive constant $c$ is the $\hat{I}”$-star. Our proof is based on induction and utilizes recent results from [F. Foucaud, T. Lehtilä. Revisiting and improving upper bounds for identifying codes. SIAM Journal on Discrete Mathematics, 2022]. We remark that there are infinitely many trees for which the bound is tight when $\hat{I}”=3$; for every $\hat{I}”\ge 4$, we construct an infinite family of trees of order $n$ with identification number very close to the bound, namely $\left(\frac{\hat{I}”-1+\frac{1}{\hat{I}”-2}}{\hat{I}”+\frac{2}{\hat{I}”-2}}\right)n>(\frac{\hat{I}”-1}{\hat{I}}”)n-\frac{n}{\hat{I}{”}^2}$. Furthermore, we also give a new tight upper bound for identification number on trees by showing that the sum of the domination and identification numbers of any tree $T$ is at most its number of vertices.