A1 Refereed original research article in a scientific journal
Identifying codes in graphs of given maximum degree: Characterizing trees
Authors: Chakraborty, Dipayan; Foucaud, Florent; Henning, Michael A.; Lehtilä, Tuomo
Publisher: Elsevier BV
Publication year: 2026
Journal:: Discrete Mathematics
Article number: 114826
Volume: 349
Issue: 2
ISSN: 0012-365X
eISSN: 1872-681X
DOI: https://doi.org/10.1016/j.disc.2025.114826
Web address : https://doi.org/10.1016/j.disc.2025.114826
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/504912859
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 Δ, the graph G admits an identifying code of size at most ([Formula presented])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 Foucaud and Lehtilä (2022) [17]. 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 ([Formula presented]. 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.
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 ([Formula presented])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 Foucaud and Lehtilä (2022) [17]. 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 ([Formula presented]. 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.
Downloadable publication This is an electronic reprint of the original article. |  |
UTU Research Portal