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
(ΔΔ−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
(Δ+Δ−22Δ−1+Δ−21)n>(ΔΔ−1)n−Δ2n. 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.