2024/03/19 by Chakraborty, Dipayan, Foucaud, Florent, Henning, Michael A. +1 · 1 citation
#05C05 #05C07 #05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2403.13172
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 Δ, the graph G admits an identifying code of size at most ( \fracΔ-1Δ )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 Δ=2 (the graph is a path or a cycle), it is long known that c=3/2 suffices. For trees, for each Δ≥ 3, we show that c=1/Δ≤ 1/3 suffices and that c is required to have a positive value only for a finite number of trees. In particular, for Δ= 3, there are 12 trees with a positive constant c and, for each Δ≥ 4, the only tree with positive constant c is the Δ-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 Δ=3; for every Δ≥ 4, we construct an infinite family of trees of order n with identification number very close to the bound, namely ( (Δ-1+(1)/(Δ-2))/(Δ+(2)/(Δ-2)) ) n > (\fracΔ-1Δ ) n -(n)/(Δ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.