Discrete Mathematics 349 (2026) 114826
Contents lists available at ScienceDirect
Discrete Mathematics  
journal homepage: www.elsevier.com/locate/disc
Identifying codes in graphs of given maximum degree: 
Characterizing trees✩,✩✩
Dipayan Chakraborty a,b,∗, Florent Foucaud a, Michael A. Henning b, 
Tuomo Lehtilä c,d,e
a Université Clermont Auvergne, CNRS, Mines Saint-Étienne, Clermont Auvergne INP, LIMOS, 63000 Clermont-Ferrand, France
b Department of Mathematics and Applied Mathematics, University of Johannesburg, South Africa
c University of Helsinki, Department of Computer Science, Helsinki, Finland
d Helsinki Institute for Information Technology (HIIT), Espoo, Finland
e University of Turku, Department of Mathematics and Statistics, Turku, Finland
a r t i c l e i n f o a b s t r a c t 
Article history:
Received 12 April 2024
Received in revised form 23 September 
2025
Accepted 25 September 2025
Available online xxxx
Keywords:
Identifying codes
Maximum degree
Trees
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 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 
(︃
Δ−1+ 1 
Δ−2
Δ+ 2 
Δ−2
)︃
n > (Δ−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.
© 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the 
CC BY license (http://creativecommons.org/licenses/by/4.0/).
✩ The first two authors were supported by the French government IDEX-ISITE initiative CAP 20-25 (ANR-16-IDEX-0001), the International Research Center 
“Innovation Transportation and Production Systems” of the I-SITE CAP 20-25, and the ANR project GRALMECO (ANR-21-CE48-0004). The research of Michael 
Henning was supported in part by the South African National Research Foundation (grant number 129265) and the University of Johannesburg. Tuomo 
Lehtilä’s research was partially supported by Business Finland project 10769/31/2022 6GTNF and Academy of Finland grants 338797 and 358718.
✩✩ Some results on the topic of this research and on a subclass of bipartite graphs have been announced in an extended abstract in the proceedings of the 
LAGOS 2023 conference [10]. We have since then been able to extend the research to all triangle-free graphs (in Part II), leading to the current presentation 
for Part I (on trees) in this paper.
* Corresponding author.
E-mail address: dipayancha@gmail.com (D. Chakraborty).
https://doi.org/10.1016/j.disc.2025.114826
0012-365X/© 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://
creativecommons.org/licenses/by/4.0/).
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
1. Introduction
A dominating set of a graph G is a set S of vertices of G such that every vertex in G is dominated by a vertex in 
S , where a vertex dominates itself and its neighbors. An identifying code is a dominating set of a graph such that any 
two vertices are dominated by distinct subsets of vertices from the identifying code. Identifying codes were introduced 
in 1998 by Karpovsky, Chakrabarty and Levitin [33], motivated by fault-detection in multiprocessor networks. Numerous 
other applications of identifying codes have been discovered such as threat location in facilities using sensor networks [44], 
logical definability of graphs [38] and canonical labeling of graphs for the graph isomorphism problem [3]. Besides, since 
the 1960s and long before the introduction of identifying codes of graphs, many related concepts such as separating systems 
or test covers have been independently discovered and studied on hypergraphs: see Rényi [42], Bondy [8], or Moret and 
Shapiro [37] for some early references. All of them put together form the general area of identification problems in graphs 
and other discrete structures, see the online bibliography [31] for over 500 papers on the topic.
Our goal is to upper-bound the smallest size of an identifying code in a graph of given maximum degree, motivated by 
a conjecture on this topic (see Conjecture 1 below). In this paper, we prove the conjecture for trees, and characterize those 
trees that are extremal for the conjectured upper bound.
Let G = (V (G), E(G)) be a graph with vertex-set V (G) and edge-set E(G). Any subset S ⊂ V (G) is called a vertex subset 
of G . The (open) neighborhood of a vertex v of G is the set NG(v) of all vertices of G adjacent to v . The vertices of G in 
NG(v) are also called the neighbors of v in G . Moreover, the set NG [v] = {v} ∪ NG(v) is called the closed neighborhood of 
v . Vertices u, v ∈ V (G) are called open (closed) twins in G if and only if they have the same open (closed) neighborhood. 
Graphs with no open or closed twins are called twin-free.
Formally speaking, an identifying code C of a graph G is a vertex subset of G that (i) dominates each vertex v of G (that 
is, either v ∈ C or v has a neighbor in C ) and (ii) separates each pair u, v of distinct vertices of G (that is, there is a vertex 
of G in C that belongs to exactly one of the two closed neighborhoods N[u], N[v]). Note that graph G admits an identifying 
code only when no two vertices of G are closed twins. Hence, we say that graphs with no closed twins are identifiable, that 
is, they admit an identifying code (for example, the whole vertex set). A vertex subset of a graph G satisfying the property 
(i) is called a dominating set of G and a subset satisfying property (ii) is called a separating set of G . It is natural to ask for a 
minimum-size identifying code of an identifiable graph G . The size, denoted by γ ID(G), of such a minimum-size identifying 
code of G is called the identification number of G . The smallest size of a dominating set of G is denoted by γ (G).
A natural question that arises in the study of identifying codes (like for the usual dominating sets) is the one of extremal 
values for the identification number: how large can it be, with respect to some relevant graph parameters? When only the 
order n of the graph is considered, it is known that the identification number of an identifiable graph with at least one 
edge lies between log2(n+ 1) [33] and n− 1 [23]; both values are tight and the extremal examples have been characterized 
in [36] and [15], respectively.
A thorough treatise on domination in graphs can be found in [25–27,29]. Bounds on domination numbers for graphs with 
restrictions on their degree parameters are a natural and important line of research. In 1996, Reed [41] proved the influential 
result that if G is a connected cubic graph of order n, then γ (G) ≤ 38n. In 2009, this bound was improved to γ (G) ≤ 5 14n, 
if we exclude the two non-planar cubic graphs of order 8 [34]. A study of independent domination in graphs with bounded 
maximum degree has received considerable attention in the literature. We refer to the breakthrough paper [12], as well as 
the papers in [11,13,20]. Another classical result is that the total domination number of a cubic graph is at most one-half 
its order [1], and the remarkable result that the total domination number of a 4-regular graph is at most three-sevenths 
its order was proved by an interplay with the notion of transversals in hypergraphs [43]. A detailed discussion on upper 
bounds on domination parameters in graphs in terms of their order and minimum and maximum degree, as well as bounds 
with specific structural restrictions imposed, can be found in [27, Chapters 6, 7, 10].
With respect to the identification number, it was observed in [15] that when the maximum degree Δ of the graph G is 
small enough with respect to the order n of the graph, the (n−1)-upper bound can be significantly improved (for connected 
graphs) to n − n 
Θ(Δ5)
. The latter was thereafter subsequently reduced to n − n 
Θ(Δ3)
in [18]. This raises the question of what 
is the largest possible identification number of a connected identifiable graph of order n and maximum degree Δ. Towards 
this problem, the following conjecture was posed; the goal of this paper is to study this conjecture.
Conjecture 1 ([16, Conjecture 1]). There exists a constant c such that for every connected identifiable graph of order n ≥ 2 and of 
maximum degree Δ ≥ 2,
γ ID(G) ≤
(︃
Δ − 1
Δ 
)︃
n + c.
Note that for Δ ≤ 1, the only connected identifiable graph is the one-vertex graph. From the known results in the 
literature, the above conjecture holds for Δ = 2 (that is, for paths and cycles) with c = 3/2 (see Theorem 5). Hence, for the 
rest of this manuscript, we assume that Δ ≥ 3.
If true, Conjecture 1 would be tight: for any value of Δ ≥ 3, there are arbitrarily large graphs of order n and maximum 
degree Δ with identification number (Δ−1
Δ 
)n, see [18,22]. A bound of the form n− n 
103(Δ+1)3 [18] proved using probabilistic 
2 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
Table 1
Trees requiring a positive constant c for Conjecture 1.
Graph class Δ c Reference 
K1,Δ Δ ≥ 3 1/Δ Lemma 9
𝒯3 3 1/3 Theorem 2
Even paths 2 1 [5] (Theorem 5) 
Odd paths 2 1/2 [5] (Theorem 5) 
arguments is the best known general result towards Conjecture 1 (for the sake of comparison, the conjectured bound can 
be rewritten as n− n 
Δ
+ c). It is reduced to n− n 103Δ for graphs with no forced vertices (vertices that are the only difference 
between the closed neighborhoods of two vertices of the graph), and to n − n f (k)Δ for graphs of clique number k [18]. 
For triangle-free graphs, this was improved to n − n 
Δ+o(Δ) in [16], and to smaller bounds for subclasses of triangle-free 
graphs, such as n − n 
Δ+9 for bipartite graphs and n − n 3Δ/(lnΔ−1) for triangle-free graphs without (open) twins. The latter 
result implies that Conjecture 1 holds for triangle-free graphs without any open twins, whenever Δ ≥ 55 (because then, 
3Δ/(lnΔ − 1) ≤ Δ). Conjecture 1 is also known to hold for line graphs of graphs of average degree at least 5 [14, Corollary 
21] as well as graphs which have girth at least 5, minimum degree at least 2 and maximum degree at least 4 [4]. Moreover, 
it holds for bipartite graphs without (open) twins by [17]. Furthermore, the conjecture holds in many cases for some graph 
products such as Cartesian and direct products [21,32,40]. See also the book chapter [35], where Conjecture 1 is presented.
Until this work, the conjecture remained open even for trees, and one of the challenges of proving it on trees was to 
allow open-twins of degree 1, which are present in many trees (note that for any set of mutual open-twins, one needs all 
of them but one in any identifying code). We will also see that almost all extremal trees for Conjecture 1 (those requiring 
c > 0) have twins. Moreover, it is known that when a tree T of order at least 3 (except the path P4) has no open twins, 
it satisfies γ ID(T ) ≤ 23n [17, Corollary 8] (this even holds for bipartite graphs). This implies the conjecture for Δ ≥ 3 for 
twin-free bipartite graphs, and clearly shows that the presence of open twins is the main difficulty in proving Conjecture 1
for trees.
Different aspects of identifying codes in trees have previously been studied in the literature, see for example [2,5–7,17, 
19,39] for some examples.
Our work. For graphs with maximum degree Δ = 2 (that is, for paths and cycles), Conjecture 1 is settled in [5] and [24] 
with the constant c = 32 . We therefore investigate Conjecture 1 when Δ ≥ 3.
Our aim is to prove Conjecture 1 for all triangle-free graphs. To ease and shorten the presentation of our proof, we split 
it into two independent papers. In the current paper, we will focus on trees, and prove Conjecture 1 (with c = 1 
Δ
≤ 13 ) for all 
trees of maximum degree at least 3 (the conjecture already holds with c = 1 for all identifiable trees of maximum degree 2, 
that is, for paths of order at least 3, due to Bertrand et al. [5]).
The main challenge for proving the conjecture, is the constant c that could, in principle, be arbitrary. Thus, in order to 
prove it for trees, a large part of our proof is dedicated to analyzing those extremal trees that require c > 0. In fact, for each 
Δ ≥ 3, we characterize the trees with maximum degree Δ for which c > 0. The number of these trees is largest for Δ = 3, 
and in fact, this case is the hardest part of our proof. The characterization is given by the collection 𝒯Δ for Δ ≥ 3, where, 
for Δ = 3, 𝒯Δ is the set of 12 trees of maximum degree 3 and diameter at most 6 depicted in Fig. 1; and 𝒯Δ = {K1,Δ} for 
Δ ≥ 4.
In the companion paper [9], we will use the results from the current paper as the starting point of a proof of Conjecture 1
for all triangle-free graphs (with the same list of trees as exceptional cases for which c > 0 is necessary when Δ ≥ 3). 
Besides Theorem 2, also our analysis about the exceptional trees from Fig. 1 will be crucial for [9].
Note that, for maximum degree at least 3, all trees are identifiable. Hence, throughout the rest of the paper, we tacitly 
assume all our trees to be identifiable. Our main results are stated as follows.
Theorem 2. Let G be a tree of order n and of maximum degree Δ ≥ 3. If G is isomorphic to a tree in 𝒯Δ, then, we have
γ ID(G) =
(︃
Δ − 1
Δ 
)︃
n + 1 
Δ
.
On the other hand, if G is not isomorphic to any tree in the collection 𝒯Δ, then we have
γ ID(G) ≤
(︃
Δ − 1
Δ 
)︃
n.
We also determine the exact value of the identification number for the exceptional trees in 𝒯Δ , as follows.
We have listed every tree requiring a positive constant c for Conjecture 1 in Table 1. In the companion paper [9], we 
show that the only other triangle-free graphs which require a positive constant c are odd cycles, and some small even-length 
cycles.
We also show that Theorem 2 is tight for many trees with c = 0, besides the list of exceptional trees mentioned above 
which require c > 0. One tight example of trees with c = 0 is the 2-corona of a path [17]. We will see that other such tight 
3 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
(a) T0: γ ID(T0) = 3 = 0.75n. (b) T1: γ ID(T1) = 5 ≈ 0.71n. (c) T2: γ ID(T2) = 5 ≈ 0.71n.
(d) T3: γ ID(T3) = 7 = 0.7n. (e) T4: γ ID(T4) = 7 = 0.7n. (f) T5: γ ID(T5) = 7 = 0.7n.
(g) T6: γ ID(T6) = 9 ≈ 0.69n. (h) T7: γ ID(T7) = 9 ≈ 0.69n. (i) T8: γ ID(T8) = 11 ≈ 0.69n.
(j) T9: γ ID(T9) = 11 ≈ 0.69n. (k) T10: γ ID(T10) = 13≈ 0.68n. (l) T11: γ ID(T11) = 15 ≈ 0.68n.
Fig. 1. The family 𝒯3 of trees of maximum degree 3 requiring c > 0 in Conjecture 1. The set of black vertices in each figure constitutes an identifying code 
of the tree.
examples exist. When Δ = 3, there are infinitely many examples for such trees. Furthermore, we give in Proposition 28
an infinite family of trees for any Δ ≥ 4 which have identification number quite close to the conjectured bound, namely 
Δ−1+ 1 
Δ−2
Δ+ 2 
Δ−2
n > (Δ−1
Δ 
)n − n 
Δ2
. In particular, as Δ increases, our construction gets closer and closer to the conjectured bound.
Structure of the paper. Following the introduction in the current section, Section 2 contains preliminary lemmas and results. 
In Section 3, we improve an upper bound from the literature, thereby relating the identifying code number of a tree with 
the usual domination number. In Section 4, we study extremal trees leading to the proof of the first part of Theorem 2. 
Section 5 is then dedicated to the proof of Theorem 2. In Section 6, we propose some constructions to deal with the 
tightness of the conjectured bound for trees. We conclude in Section 7.
2. Preliminaries
In this section, we establish notations and mention some useful results from the literature.
4 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
2.1. Definitions and notations
For any vertex v of G , the symbol degG(v) denoting the degree of the vertex v in G is the total number of neighbors of 
v in G . A leaf of a graph G is a vertex of degree 1 in G . In the literature, a leaf is also known as a pendant vertex. The (only) 
neighbor of a leaf v in a graph G is called the support vertex of v in G . The number of leaves and support vertices in G are 
denoted by ℓ(G) and s(G), respectively. Naturally, any vertex of a graph G that is not a leaf of G is usually referred to as a 
non-leaf vertex of G . The length (or the number of edges) of a longest induced path in a graph G is called the diameter of 
G and is denoted by diam(G).
On many occasions throughout this article, we shall have the need to look at a subgraph of a graph G formed by deleting 
away some vertices or edges from G . To that end, given a graph G and a set S containing some vertices and edges of G , we 
define G − S as the subgraph of G obtained by deleting from G all vertices (and edges incident with them) and edges of G
in S . For any positive integer p, let [p] denote the set {1,2, . . . , p} and for any two distinct integers p and q with p < q, let 
[p,q] denote the set {p, p + 1, . . . ,q}.
Given two sets A and B , the set A ⊖ B = (A \ B) ∪ (B \ A) is the symmetric difference of A and B . Now, let C be a vertex 
subset of G . For a given vertex v and a vertex subset C of a graph G , the intersection NG [v] ∩ C , denoted by CG [v], is 
called the C-code of v in G; and each element of the C-code of v in G is called a C-codeword (of v in G). Given a pair u, v
of distinct vertices of G such that CG [u] ⊖ CG [v] ≠ ∅, a C-codeword of either u or v in G in the non-empty symmetric 
difference CG [u] ⊖ CG [v] is called an separating C-codeword for the pair u, v in G .
One can check that the following remark holds.
Remark 3. Let G be an identifiable graph. A dominating set C of G is an identifying code of G if and only if C separates 
every pair u, v of distinct vertices of G such that dG (u, v) ≤ 2.
In light of the above Remark 3, on all occasions throughout this paper where we need to prove a dominating set C of 
an identifiable graph G to be an identifying code of G , we simply show that C separates all pairs of distinct vertices of G
with distance at most 2.
2.2. Paths
The domination number of a path Pn on n vertices is given by the following closed formula, noting that starting from 
the second vertex of the path, we add every third vertex on the path into our dominating set, together with the last vertex 
when n is not divisible by 3.
Observation 4 ([27, Observation   2.1]). If Pn is a path on n vertices, then γ (Pn) = ⌈ n 3 ⌉ ≤ n+23 .
It is known that Conjecture 1 is settled with c = 1 for all identifiable trees of maximum degree 2, that is, paths of order 
at least 3. This is due to the following result by Bertrand et al. [5]. Observe that Conjecture 1 holds for even paths with 
c = 12 and for odd paths with c = 1.
Theorem 5 ([5]). If Pn is a path on n vertices, then
γ ID(Pn) =
{︄
n 
2 + 12 , if n ≥ 1 is odd,
n 
2 + 1, if n ≥ 4 is even.
Therefore,
γ ID(Pn) =
⌊︂n 
2
⌋︂
+ 1 ≤
(︃
Δ − 1
Δ 
)︃
n + 1.
2.3. Two useful lemmas from the literature
We cite here the following two lemmas from [17], that will be essential for the proof of our main result, Theorem 2. The 
first lemma was originally proved only for trees in [28].
Lemma 6 ([17, Lemma 4]). If G is a connected bipartite graph on n ≥ 4 vertices with s support vertices and not isomorphic to a path 
P4 , then γ ID(G) ≤ n − s.
Lemma 7 ([17, Theorem 6]). If G is a connected bipartite graph on n ≥ 3 vertices and ℓ leaves, and with no twins of degree 2 or greater, 
then γ ID(G) ≤ 12 (n + ℓ).
Note that both Lemma 6 and Lemma 7 apply to trees, since trees are bipartite graphs in which the only possible twins 
are leaves sharing the same support vertex, and thus, they have degree 1.
5 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
3. An upper bound relating the identification number of a tree with its domination number
In this section, we introduce a simple new upper bound for identifying codes in trees, which improves the upper bound 
γ ID(T ) ≤ n − s from Lemma 6 (for trees), since in any graph of order at least 3, the domination number is at least the 
number of support vertices. Note that the bound of Lemma 6 was initially proved in [28] for trees only.
Theorem 8. If T is a tree other than P4 of order n ≥ 3, then γ ID(T ) ≤ n − γ (T ).
Proof. We prove the claim by induction on the order of the tree. But first, we show that the claim holds for paths. By 
Observation 4, γ (Pn) = ⌈ n 3 ⌉ ≤ n+23 . Moreover, by Theorem 5, we have γ ID(Pn) = 12 (n+2) for even n and γ ID(Pn) = 12 (n+1)
for odd n. Furthermore, we have γ ID(Pn) + γ (Pn) ≤ n+22 + n+23 = 5n+106 ≤ n, when n ≥ 10 is even and γ ID(Pn) + γ (Pn) ≤
n+1
2 + n+23 = 5n+76 ≤ n, when n ≥ 7 is odd. Hence, the claim follows for even-length paths on at least ten vertices and for 
odd-length paths on at least seven vertices. Furthermore, we have γ ID(P3)+γ (P3) = 2+1 = 3, γ ID(P5)+γ (P5) = 3+2 = 5, 
γ ID(P6) + γ (P6) = 4+ 2 = 6 and γ ID(P8) + γ (P8) = 5+ 3 = 8. Hence, the claim follows for all paths.
For n = 3, the only tree is P3 which satisfies γ ID(P3) = 2 and γ (P3) = 1, and so the bound holds. For n = 4, if T is not 
P4, then it is the star K1,3, with γ ID(K1,3) = 3 and γ (K1,3) = 1. Hence, the claim is true for n ≤ 4.
Let us next assume that the claimed bound holds for every tree T ′ other than P1, P2, P4 that has order at most n′ . 
Suppose, to the contrary, that there are trees of order n′ + 1 for which the bound does not hold. Let T be a tree of order 
n = n′ + 1 ≥ 5 such that γ ID(T ) > n − γ (T ). By the first part of the proof, the tree T is not a path.
If all vertices of T are either leaves or support vertices, then γ (T ) ≤ s(T ) and n − γ (T ) ≥ n − s(T ) and the bound of the 
statement holds by Lemma 6, a contradiction. Thus, there exists a non-support, non-leaf vertex in T . Let us root the tree at 
such a non-leaf, non-support vertex x, and let us consider the support vertex s which has the greatest distance to x. Notice 
that vertex s is adjacent to exactly one non-leaf vertex due to its maximal distance to x.
Let us first assume that s is adjacent to t ≥ 2 leaves l1, l2, . . . , lt . Consider the tree Ts = T − {s, l1, l2, . . . , lt}. Since Ts has 
n − t − 1 vertices, by induction we have γ ID(Ts) ≤ n − t − 1 − γ (Ts) unless Ts = P4, or Ts contains at most two vertices. 
However, notice that |V (Ts)| ≥ 3 on account of x being a non-leaf and non-support vertex of T . Moreover, if Ts = P4, 
then s cannot be adjacent to a support vertex of Ts , or else, the vertex x would be either a leaf or a support vertex 
of T , a contradiction to our assumption. Therefore the vertex s must be adjacent to a leaf of Ts . In this case, we have 
γ (T ) = 2 = s(T ). Since γ ID(T ) ≤ n− s(T ) by Lemma 6, the claim holds in this case. Therefore, we may assume by induction 
that there exists an identifying code Cs in Ts which has cardinality at most n − t − 1 − γ (Ts), with Ds a minimum-size 
dominating set in Ts . Furthermore, set Cs ∪ {l1, . . . , lt} is an identifying code of T , and set Ds ∪ {s} is a dominating set of T . 
Thus, γ ID(T ) ≤ n − t − 1− γ (Ts) + t ≤ n − γ (T ), as claimed.
Let us assume next that support vertex s has degree 2, and denote by u the non-leaf adjacent to s (possibly, u = x) and 
by l the leaf adjacent to s. If vertex u also has degree 2, then we consider the tree Tu = T −{l, s,u}. Since x is a non-leaf and 
non-support vertex of T , we must have |V (Tu)| ≥ 2. However, if |V (Tu)| = 2, then T is a path, a contradiction. Moreover, 
if Tu ∼ = P4, then T is path if u is adjacent to a leaf of Tu , again a contradiction. Hence, T has three support vertices and 
γ ID(T ) ≤ n− 3 (consider the identifying code formed by all non-leaf vertices of T ) while γ (T ) = 3. Hence, by induction, we 
may assume that Tu has an optimal identifying code Cu with cardinality |Cu | = γ ID(Tu) ≤ n− 3− γ (Tu) and we consider a 
minimum-size dominating set Du of Tu . Notice that Du ∪ {s} is a dominating set in T and either Cu ∪ {s,u} or Cu ∪ {l,u} is 
an identifying code in T . Hence, γ ID(T ) ≤ n − 3− γ (Tu) + 2≤ n − γ (T ) as claimed.
Therefore, we may assume from now on that degT (u) ≥ 3.
Let us next consider the case where u is a support vertex with adjacent leaf lu . Furthermore, let us consider the tree 
Ts = T − {s, l}. Notice that Ts contains at least two vertices, and if Ts contains only two vertices, then T is a path, a 
contradiction. Moreover, if Ts ∼ = P4, then u is a support vertex of P4 and γ ID(T ) = γ (T ) = 3 = n − γ (T ) (consider the set 
of non-leaf vertices as an identifying code of T ). Hence, we may apply induction to Ts and thus, there exists an optimal 
identifying code Cs of Ts of cardinality |Cs| = γ ID(Ts) ≤ n − 2 − γ (Ts). Also consider a minimum-size dominating set Ds
in Ts . Assume first that u ∈ Cs . Now set Cs ∪ {l} is an identifying code in T and Ds ∪ {s} is a dominating set in T . Thus, 
γ ID(T ) ≤ |Cs|+1 ≤ n−2−γ (Ts)+1 ≤ n−γ (T ) and we are done. Moreover, if u ∉ Cs , then lu ∈ Cs . Furthermore, in this case 
set C = (Cs ∪{s,u}) \ {lu} is an identifying code in T . Indeed, since Cs is an identifying code in Ts and NTs [lu] ∩ Cs = {lu}, we 
have |NTs [u] ∩ Cs| ≥ 2. Hence, we have |NT [u] ∩ C | ≥ 3, NT [lu] ∩ C = {u}, NT [s] ∩ C = {u, s} and NT [l] ∩ C = {s}, confirming 
that C is an identifying code of T . Moreover, we have γ ID(T ) ≤ n − γ (T ) by the same arguments as in the case where 
u ∈ Cs .
Hence, we may assume that u is not a support vertex.
Since we assumed that s is a support vertex with the greatest distance to x, there is at most one non-support vertex 
adjacent to u (on the path from u to x). Moreover, if there exists a support vertex s′ ∈ N(u) with deg(s′) ≥ 3, then we 
could have considered s′ instead of s in an earlier argument considering the case deg(s) ≥ 3. Thus, we may assume that 
every support neighbor of u has degree 2. Let us denote the support vertices adjacent to u by {s1, . . . , sh} (with s = s1) and 
the leaf adjacent to si by li for each 1 ≤ i ≤ h. Observe that the tree S Sh = T [{s1, . . . , sh, l1, . . . , lh,u}] is a subdivided star. 
Moreover, it has domination number h and identification number h + 1. Indeed, we may take the center and every support 
vertex as our identifying code Ch . Hence, the subdivided star S Sh satisfies the claimed upper bound: γ ID(S Sh) = h + 1 =
6 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
2h + 1 − γ (S Sh). Observe that if T SS = T − S Sh consists of two vertices, then T is a subdivided star S Sh+1 and the claim 
follows. If T − S Sh contains only one vertex, then u was a support vertex, contradicting our assumption. Furthermore, if 
T SS ∼ = P4, then if u is adjacent to a support vertex of P4, we may consider Ch together with the support vertices of P4
as our identifying code. If u is adjacent to a leaf of P4, then we may consider Ch together with the leaf farthest from u
and the only non-leaf vertex at distance 2 from u. In both cases, we have γ ID(T ) ≤ h + 3 = n − h − 2 since n = 2h + 5, and 
γ (T ) = h + 2. Hence, the upper bound γ ID(T ) ≤ n − γ (T ) holds. Finally, there is the case where, by induction, the tree T SS
contains an identifying code CSS of size |CSS | = γ ID(T SS ) ≤ n − (2h + 1) − γ (T SS ). However, in this case, the set CSS ∪ Ch
is an identifying code in T containing at most n − (2h + 1) − γ (T SS ) + (h + 1) = n − (h + γ (T SS )) ≤ n − γ (T ) vertices. This 
completes the proof. □
Observe that for every tree T of order at least 3, we have γ (T ) ≥ s(T ) since every leaf needs to be dominated by a 
vertex in the dominating set. Moreover, for example, in a path, we can have γ (Pn) > s(Pn). Therefore, the upper bound of 
Theorem 8 is an improvement over the simple but useful upper bound n − s(T ) from Lemma 6.
Moreover, the upper bound n − γ (T ) is tight for example for every tree in Fig. 1. This was the leading motivation for 
us to prove this bound. If we compare the upper bound of Theorem 2 to the upper bound n − γ (T ) of Theorem 8, we 
observe that in some cases, they are equal (for example for bi-stars consisting of two equal-sized stars), but in some cases 
the domination bound gives a smaller value (for example for bi-stars consisting of two unequal stars). In some cases, the 
bound from Theorem 2 is even smaller (for example for a chain of equal-sized stars joined with a single edge between 
some leaves).
4. Characterizing extremal trees
As mentioned before, the main difficulty in proving Conjecture 1 lies in handling the constant c. In this section, we focus 
on those extremal trees that require c > 0, and by a careful analysis, we are able to fully characterize them. This may seem 
a little tedious, but the analysis is crucial for the proof of Conjecture 1 for trees in Section 5, and also for the proof for all 
triangle-free graphs in the companion paper [9].
Since the identification number of paths is well-understood, for the rest of the section, we only consider graphs of 
maximum degree Δ ≥ 3. Towards proving the first part of Theorem 2, we next look at the star graphs. For any Δ ≥ 3, the 
complete bipartite graph K1,Δ is called a Δ-star, or simply a star. Noting that for any Δ-star S the set of all its leaves 
constitutes a minimum identifying code of S , it can therefore be readily verified that the following lemma is true.
Lemma 9. For a Δ-star S with Δ ≥ 3 of order n (= Δ + 1), we have
γ ID(S) =
(︃
Δ − 1
Δ 
)︃
n + 1 
Δ
.
In particular, Lemma 9 shows that Δ-stars satisfy the conjectured bound with c = 1 
Δ
. Hence, for all stars the constant 
c = 13 suffices in Conjecture 1. To fully establish the first part of Theorem 2 now, one needs to only show the veracity of the 
result for the rest of the trees in 𝒯3. To describe the trees in 𝒯3 and other graphs later in a more unified manner, we start 
by defining a particular “join” of graphs with stars. Let G ′ be a graph and S be any star. Then, let G ′ ▷v S denote the graph 
obtained by identifying a vertex v of G ′ with a leaf l of S (for example, if S and P are a 3-star and 4-path, respectively, 
each with a leaf v , then the graphs in Figs. 1(b) and 1(c) are S▷v S and P ▷v S , respectively). We call the G ′▷v S the graph 
G ′ appended with a star and it is said to be obtained by appending S (by its leaf l) onto (the vertex v of) G ′ . In the case that the 
vertex v of G ′ is inconsequential to the context or is (up to isomorphism) immaterial to the graph G , we may simply drop 
the suffix v in the notation G ′▷v S and denote it as G ′▷ S (for example, if P is a 2-path and S is a star, then P ▷v S is (up 
to isomorphism) the only graph irrespective of which vertex of the 2-path v is. Another example would be if S is a Δ-star 
and we require S ▷v S to be a graph of maximum degree Δ. As a convention, we continue to call the vertices of G ′ ▷ S by 
the same names as they were called in the graphs G ′ and S . In other words, the graph G ′ ▷ S is said to inherit its vertices 
from G ′ and S . In particular, if G ′▷ S is obtained by identifying the vertex v of G ′ and a leaf l of S , then both the names v
and l (as and when convenient) also refer to the identified vertex in G ′ ▷ S .
Let G0 be a fixed graph, p ≥ 1 be an integer and for each i ∈ [p], let Si be a Δi-star for Δi ≥ 3. Now, we may carry out 
the process of inductively appending stars by defining Gi = Gi−1▷vi−1 Si for all i ∈ [p], where vi−1 is a vertex of Gi−1. Then 
the graph Gp is called the graph G0 appended with p stars. In the case that each Si is isomorphic to a Δ-star S for Δ ≥ 3, 
we call the graph Gp the graph G0 appended with p Δ-stars. In the particular case that G0 = S0 is itself a Δ0-star for Δ0 ≥ 3, 
we simply call Gp an appended star. Further, if Δ = Δ0 = Δ1 = · · · = Δp , then we call the graph Gp an appended Δ-star.
We next furnish some general results for any identifiable graph appended with a star.
Lemma 10. If G ′ is an identifiable graph and G = G ′ ▷v S, where v is a vertex of G ′ and S is a Δ-star for Δ ≥ 3, then G is also 
identifiable and
7 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
γ ID(G) ≤ γ ID(G ′) + Δ − 1.
Proof. Graph G is clearly identifiable. Assume now that l1, l2, . . . , lΔ−1 are the leaves that G inherits from S . Also, assume 
that u is the universal vertex of S , that is, u is the common support vertex of the leaves l1, l2, . . . , lΔ−1 in G . Suppose now 
that C ′ is a minimum identifying code of G ′ . Then we claim that the set C = C ′ ∪ {l1, l2, . . . , lΔ−1} is an identifying code of 
G . Clearly, C is a dominating set of G , since C ′ is a dominating set of G ′ . Next, to check that C is also a separating set of G , 
it is enough to check that each of the vertices u, l1, l2, . . . , lΔ−1 is separated from all vertices at distance at most 2 in G by 
C . To start with, assume w to be a vertex of G other than u. Then, one can find at least one li to always be an separating 
C-codeword for the pair u,w . Moreover, each li is itself an separating C-codeword for the pair li,w , where li ≠ w . This 
establishes the claim that C is an identifying code of G . Therefore, γ ID(G) ≤ |C | = |C ′| + Δ − 1 = γ ID(G ′) + Δ − 1. This 
proves the result. □
The next lemma shows that if G is the graph obtained by starting from an identifiable “base” graph G0 and iteratively 
appending stars thereon, then the graphs G and G0 share the same constant c in Conjecture 1.
Lemma 11. Let c be a constant, G0 be an identifiable graph of order n0, of maximum degree Δ0 and be such that γ ID(G0) ≤
(
Δ0−1
Δ0
)n0 + c. For an integer p ≥ 1 and i ∈ [p], let Si be a Δi -star for Δi ≥ 3. Also, for i ∈ [p], let Gi = Gi−1 ▷vi−1 Si , where 
vi−1 is a vertex of Gi−1 , and G = Gp is a graph of order n and maximum degree Δ obtained by appending p stars to G0 . Moreover, 
assume that Δmax = max{Δi : 0≤ i ≤ p}. Then, we have
γ ID(G) ≤
(︃
Δmax − 1
Δmax
)︃
n + c ≤
(︃
Δ − 1
Δ 
)︃
n + c.
Proof. Let us prove the claim by induction on q ∈ [0, p]. Case q = 0 follows from the statement itself regarding the graph 
G0. Let us assume that the induction hypothesis holds for q ∈ [0, p − 1] and consider the case that q = p ≥ 1. We have 
G = Gp−1 ▷ Sp , where we let Gp−1 have order n′ and where Δ′max = max{Δi : 1 ≤ i ≤ p − 1}. Finally, by the induction 
hypothesis, let C ′ be a minimum identifying code of Gp−1 of cardinality at most (Δ
′
max−1
Δ′max
)n′ + c. By Lemma 10, there exists 
an identifying code C of G of cardinality |C ′| + Δp − 1. Therefore, we have
γ ID(G) ≤ |C | = |C ′| + Δp − 1 ≤
(︃
Δ′max − 1
Δ′max
)︃
n′ + c +
(︃
Δp − 1
Δp
)︃
Δp
≤
(︃
Δmax − 1
Δmax
)︃
(n − Δp) +
(︃
Δmax − 1
Δmax
)︃
Δp + c
=
(︃
Δmax − 1
Δmax
)︃
n + c
≤
(︃
Δ − 1
Δ 
)︃
n + c. □
Corollary 12. For an integer p ≥ 1 and i ∈ [0, p], let Si be a Δi -star for Δi ≥ 3. For i ∈ [p], let Gi = Gi−1 ▷vi−1 Si , where vi−1 is a 
vertex of Gi−1 , and where G = Gp is an appended star of order n and of maximum degree Δ. Moreover, assume that Δmax = max{Δi :
0 ≤ i ≤ p}. Then, we have
γ ID(G) ≤
(︃
Δmax − 1
Δmax
)︃
n + 1 
Δ0
≤
(︃
Δ − 1
Δ 
)︃
n + 1
3
.
Proof. The result follows from taking G0 = S0 in Lemma 11 and c = 1 Δ0 ≤ 13 from Lemma 9. □
It is worth mentioning here that Lemma 11 is central to our inductive proof arguments later, whereby, if a graph G is 
structurally isomorphic to a “smaller” identifiable graph G ′ appended with a star, then by using Lemma 11 for p = 1 and 
an inductive hypothesis that the “smaller” graph G ′ = G − S satisfies the conjectured bound, one can show that so does the 
“bigger” graph G . We next look at the identification numbers of the trees isomorphic to P ▷v S , where P is a path, v is a 
vertex of P and S is a star. In particular, we establish the identification numbers of the trees T2 and T3 in the collection 𝒯3.
4.1. Paths appended with stars
In this subsection, we analyze the identification numbers of paths appended with stars with respect to the conjectured 
bound. We begin by establishing the identification numbers of the trees T2 and T3 in the collection 𝒯3 illustrated in 
Figs. 1(c) and 1(d), respectively.
8 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
Lemma 13. If T2 is the tree in 𝒯3 of order n = 7 and of maximum degree Δ = 3, then
γ ID(T2) = 5 = 2
3
× 7+ 1
3
=
(︃
Δ − 1
Δ 
)︃
n + 1
3
.
Proof. Assume that T2 = P ▷z S1, where P is a 4-path, z is a leaf of P and S1 is a 3-star (see Fig. 1(c)). Assume that 
V (P ) = {w, x, y, z}, where w and z are the leaves of P with support vertices x and y, respectively. Further, assume that 
V (S1) = {u1,a1,b1, c1}, where u1 is the universal vertex of S1 and the vertices a1,b1, c1 are the three leaves of S1. Also 
assume that S1 is appended by its leaf c1 onto the leaf z of P .
We first show that any identifying code of T2 has order at least 5. So, let C be an identifying code of T2. Then C must 
contain at least two vertices each from the sets W0 = {w, x, y} and W1 = {u1,a1,b1}. Now, if either of W0 or W1 is a 
subset of C , then we are done. So, assume that exactly two vertices from each of W0 and W1 belong to C . Moreover, if 
z ∈ C , then we are done again. So, we also assume that z / ∈ C . We must have y ∈ C as the unique separating C-codeword 
for the pair x and w in G . Moreover, for C to dominate w , we need C ∩ {w, x} ≠ ∅. This implies that w ∈ C , or else, the 
pair x and y are not identified by C in G (notice that z / ∈ C by assumption). Therefore, C ∩ W0 = {w, y}. Further, for C to 
separate a1 and b1, at least one of them must be in C . So, without loss of generality, let us assume that a1 ∈ C . Then, for 
C to dominate b1, we need C ∩ {b1,u1} ≠ ∅. Now, for C to separate y and z in G , we must have u1 ∈ C (notice that x / ∈ C ). 
This implies that b1 / ∈ C (since |C ∩ W1| = 2 by our assumption). However, this implies that C does not separate u1 and a1
in G , a contradiction. Hence, |C | ≥ 5.
As for proving that the identifying number of T2 is bounded above by 5, since γ ID(P ) = 3 = 23 × 4 + 13 , taking G0 = P
and c = 13 in Lemma 11, we have γ ID(T2) ≤ 23 × 7+ 13 = 5. □
Lemma 14. If T3 is the tree in 𝒯3 of order n = 10 and of maximum degree Δ = 3, then
γ ID(T3) = 7 = 2
3
× 10+ 1
3
=
(︃
Δ − 1
Δ 
)︃
n + 1
3
.
Proof. Assume that T2 = P ▷z S1 and T3 = T2 ▷z S2, where P is a 4-path, z is a leaf of P and S1 and S2 are 3-stars (see 
Fig. 1(d)). Assume that V (P ) = {w, x, y, z}, where w and z are the leaves of P with support vertices x and y, respectively. 
Further, assume that, for i ∈ [2], V (Si) = {ui,ai,bi, ci}, where ui is the universal vertex of Si and ai,bi, ci are the three 
leaves of Si . Assume that each Si is appended by its leaf ci onto the leaf z of P . We first show that any identifying code of 
T3 has order at least 7. So, let C be an identifying code of T3. As in the proof of Lemma 13, C must contain at least two 
vertices from each of the sets W0 = {w, x, y} and Wi = {ui,ai,bi} for i ∈ [2]. Now, if any of W0, W1 and W2 are subsets of 
C , then we are done. So, assume that exactly two vertices from each of W0, W1 and W2 belong to C . Moreover, if z ∈ C , 
then we are done again. So, we also assume that z / ∈ C . Then, for both i ∈ [2], ui / ∈ C (or else, exactly one of ai and bi
belongs to C ; and thus, if ai ∈ C , without loss of generality, then z is forced to be in C as the only separating C-codeword 
for the pair ui,ai in G , contradicting our assumption that z / ∈ C ).
On the other hand, we know that the vertex y must belong to C as the only separating C-codeword for the pair w, x in 
G . Since, by our assumption, C contains exactly two vertices from W0, this forces exactly one of w and x to belong to the 
set C . Thus, if w / ∈ C , then the pair x, y has no separating C-codeword in G (since, by our assumption, z / ∈ C either); and if 
x / ∈ C , then the pair y, z has no separating C-codeword in G (since, again, for both i ∈ [2], ui / ∈ C ). Either way, we produce a 
contradiction. Hence, |C | ≥ 7.
As for proving that the identifying number of T3 is bounded above by 7, since γ ID(T2) = 5 = 23 × 7+ 13 , taking G0 = T2
and c = 13 in Lemma 11, we have γ ID(T3) ≤ 23 × 10+ 13 = 7. □
Lemmas 13 and 14 therefore establish the result in Theorem 2 for the trees T2 and T3 in the collection 𝒯3. For the rest 
of this subsection, we look at other paths appended with stars which are not isomorphic to either T2 or T3 and show that 
they satisfy Conjecture 1 with constant c = 0.
Lemma 15. Let G = P ▷v S be a graph of order n, where S is a Δ-star with Δ ≥ 3, P is a path and v is a vertex of P . If any one of the 
following properties hold
(1) P is not a 4-path; or
(2) P is a 4-path and v is a non-leaf vertex of P ; or
(3) P is a 4-path, v is a leaf of P and Δ ≥ 4,
then γ ID(G) ≤ (Δ−1
Δ 
)n.
9 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
Fig. 2. Examples for the cases in the proof of Lemma 15. The black vertices in each graph G constitute an identifying code. 
Proof. The maximum degree of G is Δ. Let P be an m-path and v denote the vertex of P to which the star S is appended. 
Let l1, l2, . . . , lΔ−1 be the leaves that G inherits from S and let u be the universal vertex of S , that is, u is the common 
support vertex of the leaves l1, l2, . . . , lΔ−1 of G . We note that n =m+ Δ. We divide the proof into cases each dealing with 
a type given in the statement. Furthermore, let v be the vertex of P adjacent to u and (if they exist) the other vertices of P
are called, from the closest vertex to u to the farthest, y, x and w .
Case 1. P is not a 4-path. We further divide this case into the following subcases.
Case 1.1. m = 2. In this case {u, v} is a dominating set in P ▷v S . By Theorem 8, we have
γ ID(P ▷v S) ≤ Δ + 2− 2 = Δ <
(︃
Δ − 1
Δ 
)︃
(Δ + 2) =
(︃
Δ − 1
Δ 
)︃
n.
See Fig. 2a for an illustration of an identifying code in P ▷v S .
Case 1.2. m ≥ 3 and m ≠ 4. Since n =m+ Δ, we have (Δ−1
Δ 
)n =m+ Δ − m 
Δ
− 1. By supposition Δ ≥ 3. When m ≥ 3, we have 
m−1
2 ≥ m3 ≥ m Δ and when m ≥ 6, we have m−22 ≥ m3 ≥ m Δ . Let us first consider odd m ≥ 3. Using Lemma 10 and Theorem 5, 
we therefore infer that
γ ID(G) ≤ γ ID(P ) + Δ − 1 = m + 1
2 
+ Δ − 1 =m + Δ − 1− m − 1
2 
≤m + Δ − 1− m 
Δ
=
(︃
Δ − 1
Δ 
)︃
n.
We now consider even m. Since m ≠ 4, we have m ≥ 6 and hence,
γ ID(G) ≤ γ ID(P ) + Δ − 1 = m + 2
2 
+ Δ − 1 =m + Δ − 1− m − 2
2 
≤m + Δ − 1− m 
Δ
=
(︃
Δ − 1
Δ 
)︃
n.
Case 2. P is a 4-path and S is appended onto one of the non-leaf vertices of P . In this case, v is a non-leaf vertex of P . Now, 
let x be the (other) non-leaf vertex of P adjacent to v . The set C = {u, v, x, l1, l2, . . . , lΔ−2} is an identifying code of G as 
illustrated in Fig. 2b. Since the identifying code C has cardinality
|C | = Δ + 1<
(︃
Δ − 1
Δ 
)︃
(Δ + 4) =
(︃
Δ − 1
Δ 
)︃
n,
the desired result follows.
Case 3. P is a 4-path, S is appended onto a leaf of P and Δ ≥ 4. In this case, v is a leaf of P . The set C = {u,w, y, l1, l2, . . . , lΔ−2}
is an identifying code of G as illustrated in Fig. 2c. Since the identifying code C has cardinality
|C | = Δ + 1<
(︃
Δ − 1
Δ 
)︃
(Δ + 4) =
(︃
Δ − 1
Δ 
)︃
n,
the desired result follows. □
Lemma 15 shows that all trees of the form P ▷ S , where P is a 4-path and S is a star, but not isomorphic to T2, satisfy 
the bound in Conjecture 1 with c = 0. The next corollary follows immediately from Lemma 15.
Corollary 16. If G = P ▷v S is a graph of order n, where P is a path, v is a vertex of P and S is a Δ-star with Δ ≥ 4, then
γ ID(G) ≤
(︃
Δ − 1
Δ 
)︃
n.
Our next lemma shows that all trees of the form T2 ▷ S , where S is a star, but not isomorphic to T3 satisfy the bound 
in Conjecture 1 with c = 0.
10 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
Fig. 3. Figures illustrating the cases in Lemma 17. The black vertices constitute an identifying code. 
Lemma 17. If G = T2▷v S is a graph of order n and of maximum degree Δ ≥ 3 such that G ≁ = T3 , where v is a vertex of T2 and S is a 
ΔS -star with ΔS ≥ 3, then
γ ID(G) ≤
(︃
Δ − 1
Δ 
)︃
n.
Proof. Clearly, ΔS ≤ Δ. We consider the following cases.
Case 1. Δ ≥ 4. Observe in this case that either ΔS = Δ or Δ = 4 and ΔS = 3. By Lemma 13, we have γ ID(T2) = 5. Therefore, 
by Lemma 10 we infer that
γ ID(G) ≤ γ ID(T2) + ΔS − 1 = ΔS + 4<
(︃
Δ − 1
Δ 
)︃
(ΔS + 7) =
(︃
Δ − 1
Δ 
)︃
n,
yielding the desired result in this case.
Thus, we assume from now on that Δ = ΔS = 3. Hence, the graph G has order n = 10 and it suffices for us to show that 
there exists an identifying code C of G of cardinality |C | = 6 < 23 × 10 = (Δ−1Δ )n. Let T2 = P ▷z S1, where P is a 4-path, z
is a leaf of P and S1 is a Δ-star for Δ ≥ 3. Assume further that
(1) V (P ) = {w, x, y, z}, where w and z are leaves of P with support vertices x and y, respectively.
(2) V (S1) = {u1,a1,b1, c1}, where u1 is the universal vertex of S1, the vertices a1,b1, c1 are the three leaves of S1 and that 
S1 is appended by its leaf c1 onto the leaf z of P .
(3) V (S) = {u, l1, l2, l3}, where u is the universal vertex of S , the vertices l1, l2, l3 are the leaves of S and l3 is the leaf of S
by which the latter is appended onto the vertex v of T2.
Since Δ = ΔS = 3, S is not appended onto the universal vertex u1 of S1. We consider next two further cases.
Case 2. S is appended onto either of the leaves a1 and b1 of S1 . Without loss of generality, let us assume that S is appended 
onto the leaf a1 of T2. The set C = {y,w,u1,u,a1, l1} is an identifying code of G of cardinality 6 as illustrated in Fig. 3a, 
where the vertices in the identifying code are marked with black, implying that γ ID(G) ≤ 6 < 23 ×10 = (Δ−1Δ )n, yielding the 
desired result.
Case 3. S is appended onto any vertex of T2 other than u1 , a1 and b1 . In this case, since G ≁ = T3, the star S cannot be appended 
onto the vertex z of T2 (that is, v ≠ z). Thus, S is appended onto either of the vertices w , x and y of T2. We further divide 
this case into the following subcases.
Case 3.1. S is appended onto either of the non-leaf vertices x or y of T2 . In this case, the graph G can also be expressed as 
G = G ′ ▷z S1, where G ′ = P ▷v S . Since the maximum degree of G ′ is ΔS = 3, by Lemma 15(2), we have
γ ID(G ′) ≤ 2
3
|V (G ′)| = 2
3
(n − 3).
The bound for G therefore follows with Lemma 10.
Case 3.2. S is appended onto the leaf w of T2 . In this case, the set C = {a1,u1, z, w,u, l1} is an identifying code of G of 
cardinality 6 as illustrated in Fig. 3b where the vertices in the identifying code are marked with black, implying that 
γ ID(G) ≤ 6 < (Δ−1
Δ 
)n, as desired. □
Finally, the next lemma shows that all trees of the form T3 ▷ S , where S is a star, also satisfy the bound in Conjecture 1
with c = 0.
Lemma 18. If G = T3 ▷v S is a graph of order n and of maximum degree Δ ≥ 3, where v is a vertex of T3 and S is a ΔS -star with 
ΔS ≥ 3, then
11 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
γ ID(G) ≤
(︃
Δ − 1
Δ 
)︃
n.
Proof. Let P be a 4-path and let S1 and S2 be 3-stars such that V (P ) = {w, x, y, z}, where w and z are leaves of P with 
support vertices x and y, respectively. Moreover, for i ∈ [2], we have V (Si) = {ui,ai,bi, ci}, where ui is the universal vertex 
of Si , and the vertices ai,bi, ci are the three leaves of Si . Also assume that each Si is appended by its leaf ci onto the leaf 
z of P to form the tree T3. Now, let T2 ∼ = P ▷z S1 and we have T3 ∼ = (P ▷z S1)▷z S2. Let us assume first that S is also 
appended onto the vertex z of P (that is, v = z). In this case, degG(z) = 4. If ΔS = 3, then n = 13 and by Lemma 10, we 
have
γ ID(G) ≤ γ ID(T3) + 2 = 9< 3
4
× 13 =
(︃
Δ − 1
Δ 
)︃
n.
This implies that S is a Δ-star with Δ ≥ 4. Let G ′ = P ▷z S have order n′ (= n − 6) and maximum degree Δ′ ≤ Δ. By 
Corollary 16, we have
γ ID(G ′) ≤
(︃
Δ′ − 1
Δ′
)︃
n′ ≤
(︃
Δ − 1
Δ 
)︃
(n − 6).
Therefore, by Lemma 11, we have the result.
So, let us assume that G ′′ = T2 ▷v S has order n′′ (= n − 3) and maximum degree Δ′′ ≤ Δ, where S is appended onto a 
vertex of T2 other than z (that is, v ≠ z). In that case, the graph G ′′ ≁ = T3 and, therefore, by Lemma 17, we have
γ ID(G ′′) ≤
(︃
Δ′′ − 1
Δ′′
)︃
n′′ ≤
(︃
Δ − 1
Δ 
)︃
(n − 3).
Therefore, we have the result by Lemma 11. □
To conclude the subsection, we close with the following remark.
Remark 19. If G is a graph isomorphic to a path appended with stars, then G satisfies Conjecture 1 with c = 13 in the case 
of T2 and T3, and with c = 0 otherwise.
4.2. Appended stars
The trees in the collection 𝒯3 other than T2 and T3 are precisely the appended 3-stars of maximum degree 3 and of 
diameter at most 6. In this subsection, we show that all appended stars satisfy the conjectured bound with c = 0, except 
for those in 𝒯3, which satisfy the bound with c = 13 . To start with, we first look at appended stars of maximum degree at 
least 4.
Lemma 20. If G is an appended star of order n and of maximum degree Δ ≥ 4, then
γ ID(G) ≤
(︃
Δ − 1
Δ 
)︃
n.
Proof. Let p be an integer and, for i ∈ [0, p], let Si be a Δi-star with Δi ≥ 3. Also, for i ∈ [p], let Gi = Gi−1 ▷vi−1 Si , where 
vi−1 is a vertex of Gi−1, and such that G = Gp is the appended star. Let V (Si) = {ui, li1, . . . , liΔi }, where ui is the universal 
vertex and each lij , for j ∈ [Δi], is a leaf of Si . For h ∈ [p], let Gh have order n′ and maximum degree Δ′ . Observe that if 
γ ID(Gh) ≤ (Δ′−1Δ′ )n′ , then γ ID(G) ≤ (Δ−1Δ )n by Lemma 11. We next look at the following two cases according to whether 
the Δi ’s are all equal or not.
Case 1. There exists 1 ≤ h ≤ p such that Δ0 = Δ1 = · · · = Δh−1 ≠ Δh. Let Gh−1 = G ′′ have order n′′ and maximum degree Δ′′ . 
Moreover, let C ′′ be a minimum identifying code of G ′′ .
Case 1.1. Δh = Δh−1 + q for some q > 0. Observe that
n′′ = hΔ0 + 1 and n′ = n′′ + Δh = (h + 1)Δh − hq + 1.
By Corollary 12, we have
|C ′′| ≤
(︃
Δ0 − 1
Δ0
)︃
n′′ + 1 
Δ0
= h(Δ0 − 1) + 1 = h(Δh − q − 1) + 1.
Moreover, by Lemma 10, we have
12 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
γ ID(Gh) ≤ |C ′′| + Δh − 1 ≤ h(Δh − q − 1) + 1+ (Δh − 1)
=
(︃
Δh − 1
Δh
)︃
hΔh − hq + Δh
=
(︃
Δh − 1
Δh
)︃
(n′ − Δh + hq − 1) − hq + Δh
=
(︃
Δh − 1
Δh
)︃
n′ − (hq − 1) 1 
Δh
≤
(︃
Δ′ − 1
Δ′
)︃
n′.
Case 1.2. Δh = Δh−1 − q for some q > 0. Observe that
n′′ = hΔ0 + 1 and n′ = n′′ + Δh = (h + 1)Δ0 − q + 1.
By Corollary 12, we have
|C ′′| ≤
(︃
Δ0 − 1
Δ0
)︃
n′′ + 1 
Δ0
= h(Δ0 − 1) + 1.
Moreover, by Lemma 10, we have
γ ID(Gh) ≤ |C ′′| + Δh − 1 ≤ h(Δ0 − 1) + Δ0 − q
=
(︃
Δ0 − 1
Δ0
)︃
hΔ0 + Δ0 − q
=
(︃
Δ0 − 1
Δ0
)︃
(n′ − Δ0 + q − 1) + Δ0 − q
=
(︃
Δ0 − 1
Δ0
)︃
n′ − q − 1
Δ0
≤
(︃
Δ0 − 1
Δ0
)︃
n′ ≤
(︃
Δ′ − 1
Δ′
)︃
n′.
In both the above subcases therefore, the result follows from Lemma 11. This completes the proof of Case 1.
Case 2. Δ0 = Δ1 = · · · = Δp . In this case, we have n = (p + 1)Δ0 + 1 and n′ = (h + 1)Δ0 + 1. Let us now divide our analysis 
into the following subcases.
Case 2.1. For some i ∈ [p], the vertex vi−1 ∈ {u0,u1, . . . ,ui−1}. This subcase implies that the star Si is appended onto a universal 
vertex of any of the stars S0, S1, . . . , Si−1. Then by a possible renaming of the stars, let us assume that v0 = u0 is the 
universal vertex of S0. We then take h = 1 and look at the graph G1 = S0 ▷u0 S1. Therefore, we have Δ′ = Δ0 + 1 ≥ 4. The 
set C ′ consisting of all the leaves of G1 is an identifying code of G1. Therefore, we have
γ ID(G1) ≤ |C ′| = 2Δ0 − 1 =
(︃
Δ0
Δ0 + 1
)︃
(2Δ0 + 1) − 1 
Δ0 + 1 ≤
(︃
Δ′ − 1
Δ′
)︃
n′.
Replacing G0 by G1 in Lemma 11, yields the desired result.
Case 2.2. For each 1≤ i ≤ p, the star Si is appended onto a leaf of Gi−1 . This subcase can be further divided according to whether 
Δ0 ≥ 4 or Δ0 = 3.
Case 2.2.1. Δ0 ≥ 4. We again take h = 1 and consider the graph G1 of order n′ = 2Δ0 + 1 with Δ′ = Δ0 ≥ 4. In this case, 
G1 has 2Δ′ − 2 leaves, a single degree 2 vertex, namely l21, and two degree Δ′ vertices, namely u1 and u2. The set C ′ =
{u1,u2, l12, . . . , l1Δ′−1, l22, . . . , l2Δ′−1} is an identifying code of G1. Moreover, we have
|C ′| = 2(Δ′ − 1) =
(︃
Δ′ − 1
Δ′
)︃
n′ − Δ
′ − 1
Δ′
<
(︃
Δ′ − 1
Δ′
)︃
n′.
Therefore, again replacing G0 by G1 in Lemma 11, the result follows.
Case 2.2.2. Δ0 = 3. Since Δ ≥ 4, this implies, again by a possible renaming of the stars, that the graph G3 is obtained by 
appending the stars S1, S2 and S3 onto a single leaf l01, say, of S0. The set C
′ = {l01, l02, l11, l21, l31,u0,u1,u2,u3} is an identifying 
code of G3. This implies that
13 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
Fig. 4. Tree T7 ∈ 𝒯3: diam(T7) = 6 and γ ID(T7) = 9. The set of black vertices constitutes an identifying code of T7. 
|C ′| = 9< 3
4
× 13 ≤
(︃
Δ′ − 1
Δ′
)︃
n′.
Hence, again replacing G0 by G3 in Lemma 11, the result follows. □
The preceding lemma shows that if we require c > 0 in the conjectured bound for an appended star, then the appended 
star must be subcubic. For the rest of this subsection, therefore, we investigate the veracity of Conjecture 1 for appended 
3-stars of maximum degree 3. Before that, one can verify the following.
Remark 21. The diameter of a subcubic appended 3-star is even.
We now look at the appended 3-stars in 𝒯3 in the following proposition, which proves that the trees in 𝒯3 satisfy the 
conjectured bound with c = 13 .
Proposition 22. If G is an appended 3-star of order n, of maximum degree Δ = 3 and of diameter at most 6, then
γ ID(G) = 2
3
n + 1
3
.
Proof. For diam(G) = 2, that is, G being a 3-star itself, the result follows from Lemma 9. We therefore consider diam(G) >
2, that is, by the parity of diam(G) by Remark 21, only the cases where diam(G) is either 4 or 6. We first show that 
γ ID(G) ≥ 23n+ 13 . Let p be an integer and for each i ∈ [0, p], let Si be a 3-star. Also, for i ∈ [p], let Gi = Gi−1▷vi−1 Si , where 
vi−1 is a vertex of Gi−1, and where G = Gp is the appended 3-star.
Suppose, to the contrary, that G (with diameter either 4 or 6) is a counterexample of minimum order such that γ ID(G) <
2
3n + 13 . Since diam(G) is either 4 or 6, there exists a 3-star S0, say, such that G is obtained by appending other 3-stars to 
the leaves of S0 only (notice that, for G to be subcubic, no 3-star S j is appended onto the universal vertex of another 3-star 
Si). For each i ∈ [0, p], let V (Si) = {ui,ai,bi, ci}, where ui is the universal vertex and ai,bi, ci are the leaves of Si . Moreover, 
assume that each Si is appended by its leaf ci onto the graph Gi−1. Then, for all i ∈ [p], ai and bi are leaves of G adjacent 
to the common support vertex ui (see Fig. 4 for the tree T7 ∈ 𝒯3 as a sample appended 3-star of diameter at most 6; also 
refer to Fig. 1(a) and Figs. 1(d)-1(k) for other such examples). Now, assume C to be a minimum identifying code of G . Then, 
we claim the following.
Claim 22.A. For each i ∈ [p], the universal vertex ui of the 3-star Si belongs to C .
Proof of Claim. Suppose, to the contrary, that ui / ∈ C for some i ∈ [p]. For the vertices ai and bi , both of which have degree 1
in G , to be dominated by C , we must have ai ,bi ∈ C . Now, observe that, by a possible renaming of the stars S1, S2, . . . , Sp , 
we can assume that up / ∈ C and that ap,bp ∈ C . Let C ′ = C \ {ap,bp}. Then, C ′ is an identifying code of Gp−1. Noting that 
n = 3p + 4 and |C | < 23n + 13 , we have
|C ′| = |C | − 2< 2
3
n − 5
3
= 2
3
(3p + 4) − 5
3
= 2p + 1
=⇒ |C ′| ≤ 2p < 2p + 2
3
= 2
3
(3p + 1) = 2
3
(n − 3).
However, since Gp−1 has order n − 3, this contradicts the minimality of the order of G . Thus, we must have ui ∈ C for all 
i ∈ [p]. ⧫
Claim 22.A implies that, for each i ∈ [p], at least two vertices from each set {ai,bi, ci}, in addition to ui , must belong to 
C (otherwise the vertices of Si are not separated). However, if both ai,bi ∈ C , then we can discard bi from C and include 
ci (if not included already) in the identifying code C of G . In this way, C still remains an identifying code of G and of 
order at most the same as before. In particular then, for each i ∈ [p], we can assume that {ui,ai, ci} ⊂ C . Next, we prove the 
following claim.
Claim 22.B. |C | ≥ 2p + 3.
14 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
Fig. 5. Graph Z : γ ID(Z) = 8. The set of black vertices constitutes an identifying code of Z . 
Proof of Claim. If diam(G) = 4, then in this case, p ≤ 2 and onto exactly one leaf c0, say, of S0 at least one other 3-
star S1, say, is appended by its leaf c1. However then at least two vertices from {u0,a0,b0} must be in C . By the above 
considerations following the proof of Claim 22.A, we have at least 2p+1 further vertices in C , and thus |C | ≥ 2p+3. Hence, 
we may assume that diam(G) = 6, for otherwise the desired lower bound in the claim follows. In this case, p ≤ 6 and to at 
least two leaves a0 and c0 of S0, other 3-stars are appended. Then again, by our previous observation, a0 and c0 are included 
in the identifying code C , since a0 = ci for some i ≠ 0 and c0 = c j for some j ≠ 0. Moreover, for b0 to be dominated by C , 
at least one of {u0,b0} must be in C . Thus, we again have |C | ≥ 2p + 3. This proves the claim. ⧫
Finally, again noting that n = 3p + 4, we have by Claim 22.B that
γ ID(G) = |C | ≥ 2p + 3 = 2
3
(3p + 3) + 1 = 2
3
n + 1
3
,
contradicting our initial supposition that γ ID(G) < 23n+ 13 . Hence, γ ID(G) ≥ 23n+ 13 . On the other hand, by Corollary 12, we 
have γ ID(G) ≤ 23n + 13 . Consequently, γ ID(G) = 23n + 13 . □
We now turn our attention to the appended 3-stars of diameter strictly larger than 6, that is, at least 8 (by the parity 
of the diameter in Remark 21). To that end, we first show in the next lemma the existence of a special appended 3-star of 
diameter 8.
Lemma 23. Let each of S0, S1, S2, S3 be a 3-star. Let G0 = S0 and, for i ∈ [3], let Gi = Gi−1 ▷vi−1 Si , where vi−1 is a vertex of Gi−1. 
Finally, let Z = G3 be a subcubic appended 3-star of diameter 8. Then, up to isomorphism, the graph Z is unique.
Proof. Since Z = G2 ▷v2 S3 and diam(Z) = 8, it follows that diam(G2) = 6. Next, to obtain G2, assume, without loss of 
generality, that S1 and S2 are appended onto two distinct leaves of S0. Then, the longest path in G2 (with path-length of 
diam(G2)) has one leaf each of S1 and S2 as its endpoints. Thus, S3 is appended onto a leaf of G2 that is also a leaf of 
either S1 or S2 (see Fig. 5). This completes the proof. □
In the following lemma we establish the identification number of the graph Z constructed in the statement of Lemma 23.
Lemma 24. If Z is the unique subcubic appended 3-star of diameter 8 as defined in the statement of Lemma 23, then γ ID(Z) = 8 <
2
3 |V (Z)|.
Proof. For 0 ≤ i ≤ 3, let V (Si) = {ui,ai,bi, ci} such that ui is the universal vertex and ai,bi, ci are the three leaves of Si . 
To obtain Z (up to isomorphism), let us assume that the 3-stars are appended in such a manner that the following pairs 
of vertices are identified: (c0, c1), (a0, c2) and (a1, c3) (see Fig. 5). To first show that γ ID(Z) ≤ 8, it is enough to check that 
the set {u0,u1,u2,u3,a0,a1,a2,a3} is an identifying code of Z (again, see Fig. 5 for the identifying code represented by the 
black vertices). We next show the reverse that γ ID(Z) ≥ 8. Let C be a minimum-size identifying code in Z .
Claim 24.A. If c0 ∉ C , then |C | ≥ 8.
Proof of Claim. Let G ′ = G − {c0}. Observe that G ′ consists of two identical components of order 6. We show that each of 
them has at least four vertices in the identifying code. First of all, a0 ∈ C is forced as the only vertex which separates u0
and b0. Moreover, |{u0,b0} ∩ C | ≥ 1 since C dominates b0. Finally, we have |{a2,u2,b2} ∩ C | ≥ 2 to dominate and separate 
a2 and b2. Thus, |C | ≥ 8. ⧫
Claim 24.B. If c0 ∈ C , then |C | ≥ 9.
15 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
Proof of Claim. We again show that |C ∩ {u0,b0,a0,u2,a2,b2}| ≥ 4 and the claim follows from symmetry. If u2 ∉ C , then in 
this case, we need a2,b2 ∈ C to dominate them and we also need two vertices from {a0,u0,b0}. Indeed, a single vertex can 
dominate all of these three vertices only if it is u0. However, u0 does not separate a0 and b0, implying that |C | ≥ 9. On the 
other hand, if u2 ∈ C , then in this case, we have a2 or b2 in C . We may assume without loss of generality that a2 ∈ C . To 
separate u2 and a2, we also need a0 or b2 in C . Thus, |C ∩ {a2,b2,u2,a0}| ≥ 3. Finally, we need u0 or b0 in C to dominate 
b0, once again implying that |C | ≥ 9. ⧫
The lemma follows from these two claims. □
The above lemma shows that the graph Z satisfies Conjecture 1 with c = 0. We end this section with the following 
lemma which shows that all appended 3-stars of maximum degree 3 other than those in the collection 𝒯3 (that is, with 
diameter at least 8) satisfy the conjectured bound with c = 0.
Lemma 25. If G is an appended star of order n, of maximum degree Δ = 3 and of diameter at least 8, then
γ ID(G) ≤ 2
3
n =
(︃
Δ − 1
Δ 
)︃
n.
Proof. Since diam(G) ≥ 8, the graph G must contain the graph Z (of Lemma 24) as an induced subgraph. Taking G0 = Z in 
Lemma 11, the result follows. □
We summarize the current subsection with the following remark.
Remark 26. If G is an appended star, then G satisfies Conjecture 1 with c = 13 if G is isomorphic to a tree in 𝒯3 and with 
c = 0 otherwise.
We also state the following proposition, which will be useful in our proofs.
Proposition 27. If T is a tree in 𝒯3, then the following properties hold.
(i) If T ≠ T2 , then T has an optimal identifying code C(T ) containing all vertices of degree at most 2.
(ii) If T / ∈ {T2, T3}, then C(T ) can be chosen as an independent set which contains every vertex of degree at most 2. When we delete 
any code vertex v from T , set C(T ) \ {v} forms an optimal identifying code of the forest T − v.
Proof. The constructions in the claim can be confirmed by the identifying codes provided in Fig. 1. Their optimality follows 
from Lemmas 9, 13, 14 and Proposition 22. □
5. Proof of Theorem 2
We are now ready to prove Theorem 2. The proof first utilizes Lemmas 6 and 7, using which, we can show that one 
needs to consider only the trees G of the form G ′ ▷v S , whereby G ′ is necessarily a tree as well. Induction plays a central 
role in proving Theorem 2.
Proof of Theorem 2. The proof is by induction on the order n of the tree G . Since we have Δ ≥ 3, this implies that n ≥ 4. 
However, n = 4 implies that G is a 3-star and thus is isomorphic to a graph in 𝒯3. Therefore, we take the base case of the 
induction hypothesis to be when n = 5. In the base case now, for G to be a tree and non-isomorphic to a star, we must 
have G ∼ = P ▷ S , where P is a 2-path and S is a 3-star. Therefore, by Lemma 15(1), the result is true in the base case. Let us 
assume that the induction hypothesis is true for all trees G ′′ on n′′ vertices such that 5 ≤ n′′ < n, not isomorphic to a tree 
in 𝒯Δ′′ , of maximum degree Δ′′ ≥ 3. Let ℓ and s be the number of leaves and support vertices, respectively, in G . First of 
all, if s ≥ n 
Δ
, then, by Lemma 6, we have
γ ID(G) ≤ n − s ≤ n − 1 
Δ
n =
(︃
Δ − 1
Δ 
)︃
n
and, hence, we are done. Moreover, if ℓ ≤ (Δ−2
Δ 
)n, then, by Lemma 7, we have
γ ID(G) ≤ n + ℓ
2 
≤
(︂
1+ Δ − 2
Δ 
)︂n 
2
=
(︃
Δ − 1
Δ 
)︃
n
and we are done in this case too. We therefore assume that both s < n 
Δ
and that ℓ > Δ−2
Δ 
n. The latter inequality implies 
that there is at least one leaf and, hence, at least one support vertex as well in G . In this case, the average number, ℓs , of 
16 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
leaves per support vertex satisfies ℓs > Δ − 2. Moreover, as G is not isomorphic to a star, the maximum number of leaves 
adjacent to a support vertex is Δ − 1. Hence, there exists at least one support vertex which is adjacent to exactly Δ − 1
leaves. Therefore, we must have G ∼ = G ′ ▷x S , where G ′ is also a tree, x is a vertex of G ′ and S is a Δ-star. Let n′ = |V (G ′)|
and Δ′ be the maximum degree of G ′ . We proceed further with the following claim.
Claim  2.A. If n′ ≤ 4, then γ ID(G) ≤ (Δ−1
Δ 
)n.
Proof of Claim. Suppose that n′ ≤ 4. If n′ = 1, then G is a Δ-star by itself and, hence, G is isomorphic to a graph in 𝒯Δ , a 
contradiction. If n′ = 2, then since G ′ is connected, we have G ′ ∼ = P2. Therefore, G ∼ = P ▷ S , where P is a 2-path and S is a 
Δ-star, and the desired upper bound follows by Lemma 15(1). If n′ = 3, then since G ′ is a tree, G ′ ≁ = K3 and, thus, G ∈ P ▷ S , 
where P is a 3-path, and once again, by Lemma 15(1), the desired result holds. Hence, we may assume that n′ = 4.
Since G ′ is a tree, G ′ can be isomorphic to either a 4-path or a 3-star. Let us, therefore, assume that G ′ is isomorphic 
to either a 4-path P , say, or a 3-star S1, say. If G ′ ∼ = P , then by the fact that G is not isomorphic to the graph T2 in 𝒯3, 
we must have G ∼ = P ▷x S , where x is a non-leaf vertex of P . In this case, by Lemma 15(2), the result holds. If, however, 
G ′ ∼ = S1, then G ∈ S1 ▷x S , where x is a vertex of S1. If x is a leaf of S1 and Δ = 3, then G ∼ = T1 in the collection 𝒯3, a 
contradiction. Therefore, in the case that either x is a non-leaf vertex of S1 or that Δ ≥ 4, we are done by Lemma 20. ⧫
By Claim 2.A, we may assume that n′ ≥ 5, for otherwise the desired result follows. Now, if Δ′ = 2, then G ′ is a path of 
order at least 5 and hence, we are done by Lemma 15(1). Hence we may assume in what follows that Δ′ ≥ 3.
Claim  2.B. If G ′ is isomorphic to a graph in 𝒯Δ′ , then γ ID(G) ≤ (Δ−1Δ )n.
Proof of Claim. Suppose that G ′ is isomorphic to a graph in 𝒯Δ′ . If G ′ is isomorphic to a star in 𝒯Δ′ , then G ′ ∼ = S ′ , where 
S ′ is a Δ′-star. Since n′ ≥ 5, we must have Δ′ ≥ 4, implying that G ∼ = S ′ ▷ S , and the desired upper bound follows from 
Lemma 20. If G ′ is isomorphic to T2, then G = T2 ▷ S . However, as G ≁ = T3 ∈ 𝒯3, the result follows by Lemma 17. If G ′ is 
isomorphic to T3, then in this case, G = T3 ▷ S and hence, the result holds by Lemma 18.
Hence, we may assume that G ′ is isomorphic to an appended 3-star in 𝒯3. Thus, G is an appended star. If Δ ≥ 4, then 
we are done by Lemma 20. Hence we may assume that Δ = 3, implying that G is an appended 3-star itself. However, for G
not to be isomorphic to any graph in 𝒯Δ , the tree G must be an appended 3-star of diameter at least 8 and in which case, 
by Lemma 25, we are done. ⧫
By Claim 2.B, we may assume that G ′ is not isomorphic to any tree in 𝒯Δ′ , for otherwise the desired result follows. Since 
n′ ≥ 5 and Δ′ ≥ 3, by the induction hypothesis, we have
γ ID(G ′) ≤
(︃
Δ − 1
Δ 
)︃
n′.
Thus, by Lemma 11, the result holds. □
6. Tightness of the bound for trees
In this section, we consider some trees for which Conjecture 1 is tight. Clearly, Conjecture 1 is tight for every graph in 
𝒯Δ (with c = 1/Δ).
Moreover, it is tight for some infinite families (with c = 0), such as double stars with 2Δ − 2 leaves, where by a double 
star we mean a tree G = S1 ▷u S2, where S1 is a (Δ − 1)-star, S2 is a Δ-star and u is universal vertex of S1. The double 
star G has n = 2Δ vertices and the smallest identifying code C of G has 2Δ − 2 code vertices. Thus, |C | = (Δ−1
Δ 
)n.
Another class of trees for which the conjecture is tight when Δ = 3 is the 2-corona of a path P (see [17] or [30, 
Section 1.3]). We obtain the 2-corona of a graph G by identifying each vertex v of G with a leaf of a 3-vertex path P v .
We also believe that more examples can be built using the appended stars and paths constructions from Section 4.
Moreover, in the regime when both n and Δ are large, we next show that there are trees which almost attain the 
conjectured bound. Notice that when Δ is large, the value 
Δ−1+ 1 
Δ−2
Δ+ 2 
Δ−2
is roughly Δ−1
Δ 
.
Proposition 28. Let Pt be a path of order t ≥ 3 and let Δ ≥ 4 be an integer. Let an intermediate tree of order n be formed by appending 
onto every vertex of the path Δ − 2 ≥ 2 copies of Δ-stars. Thereafter, for each vertex pi of the path, subdivide a single edge between 
pi and an adjacent support vertex of the intermediate tree. If Tt,Δ denotes the resulting tree (see Fig. 6 for an example with t = 6 and 
Δ = 4), then
γ ID(Tt,Δ) =
(︄
Δ − 1+ 1 
Δ−2
Δ + 2 
Δ−2
)︄
n >
(︃
Δ − 1
Δ 
)︃
n − n 
Δ2
.
17 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
Fig. 6. Tree Tt,Δ as in Proposition 28 with t = 3 and Δ = 4. The set of black vertices constitutes an identifying code of Tt,Δ . 
Proof. Let T = Tt,Δ . For each j ∈ [t], let p j be a vertex in the path Pt and let S ji for i ∈ [Δ−2] be Δ-stars appended onto p j . 
Moreover, let u j1 be the universal vertex of S
j
1 and let the edge u
j
1p j of the intermediate tree be subdivided by the vertex v
j
1
of T . We then have n = t(Δ−2)Δ+2 · t and the maximum degree of T is Δ. Observe that any identifying code of T requires 
at least Δ − 1 codewords from each star S ji . Furthermore, we need an additional codeword to dominate v j1 (if the center of 
S j1 is not chosen yet) or to separate v
j
1 from a leaf of S
j
1 (if the center of S
j
1 is chosen but some leaf of S
j
1 is not). Thus, 
there are at least (Δ − 2)(Δ − 1) + 1 codewords among the vertices in V j(Pt) = {p1, v j1} ∪ V (S j1) ∪ V (S j2) ∪ · · · ∪ V (S jΔ−2). 
Moreover, we have |V j(Pt)| = (Δ − 2)Δ + 2. Thus,
γ ID(T )
n 
≥ (Δ − 2)(Δ − 1) + 1
(Δ − 2)Δ + 2 =
Δ − 1+ 1 
Δ−2
Δ + 2 
Δ−2
.
Moreover, we notice that we may choose as an identifying code of this size, all the leaves and all the path vertices (as 
illustrated in Fig. 6 by the set of black vertices). Therefore,
γ ID(T )
n 
= Δ − 1+
1 
Δ−2
Δ + 2 
Δ−2
.
We note that
Δ − 1+ 1 
Δ−2
Δ + 2 
Δ−2
= 1 
Δ
(︄
Δ2 − Δ + Δ 
Δ−2
Δ + 2 
Δ−2
)︄
= 1 
Δ
(︃
Δ3 − 3Δ2 + 3Δ
Δ2 − 2Δ + 2 
)︃
=Δ − 1
Δ 
− Δ − 2 
Δ3 − 2Δ2 + 2Δ
>
Δ − 1
Δ 
− Δ − 2 
Δ2(Δ − 2)
=Δ − 1
Δ 
− 1 
Δ2
.
Hence, the claimed inequality holds. □
In the previous proposition, we could obtain a slightly better result by adding an additional star for each end of the 
path. However, that improvement would be of local nature and hence, would improve the result only by a constant while 
complicating the proof. Note that we may modify the tree Tt,Δ by adding an edge between the two endpoints of the 
underlying path Pt . The resulting graph has the same identification number as the tree Tt,Δ .
Previously, in [5], an exact value for the identification number of complete q-ary trees was given. Later in [16], the 
authors showed that in terms of maximum degree, the complete (Δ − 1)-ary tree TΔ has identification number
γ ID(TΔ) =
⌈︄(︄
Δ − 2+ 1 
Δ
Δ − 1+ 1 
Δ
)︄
n
⌉︄
.
18 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
When we compare this value to the one in Proposition 28, we observe that it has slightly smaller multiplier in front of n.
An observant reader may notice that the root of the tree TΔ has degree of only Δ − 1. Hence, we might gain slight 
improvements by adding some new subtree to it. Let r be the root of tree TΔ and let T ′ be another tree which we join with 
an edge to r. Let CΔ (resp., C ′) be an identifying code in TΔ (resp. T ′). Then, C = CΔ ∪ C ′ ∪ {r} is an identifying code in the 
combined tree. Furthermore, we may interpret the size of the identifying code also as the density of the identifying code 
in the graph. In particular, we can observe that the density of the code in the combined tree is increased by a meaningful 
amount if and only if tree T ′ is large and a minimum identifying code of T ′ has a density larger than that of a minimum 
identifying code in TΔ . In other words, the tree T ′ alone is a better example for a tree with large identifying code than the 
tree TΔ . Hence, tree TΔ does not help in finding a larger example than we have found in Proposition 28.
Another observation we make is that when n is large and Δ = 4, Proposition 28 gives γ ID(Tt,4) = 7 10n. We do not know 
any large triangle-free constructions with significant improvements for this case.
7. Conclusion
We have made significant progress towards Conjecture 1 by proving it for all trees; moreover we have precisely charac-
terized the trees that need c > 0 in the conjectured bound. It is interesting that for every fixed Δ ≥ 3, there is only a finite 
list of such trees. We close with the following list of open questions and problems.
Question 1. For every fixed Δ ≥ 3, if G is a connected identifiable graph of order n and of maximum degree Δ, then is it true that
γ ID(G) ≤
(︃
Δ − 1
Δ 
)︃
n,
except for a finite family of graphs?
Problem 1. Characterize the trees T of order n with maximum degree Δ satisfying
γ ID(T ) =
(︃
Δ − 1
Δ 
)︃
n.
Problem 2. Characterize the trees T of order n ≥ 3 satisfying γ ID(T ) = n−γ (T ), that is, characterize the trees T that achieve 
equality on the upper bound in Theorem 8.
Problem 3. Determine classes of graphs G of order n ≥ 3 satisfying γ ID(T ) ≤ n − γ (T ), that is, does Theorem 8 hold for a 
larger class of graphs (for example some subclass of bipartite graphs containing all trees)?
As mentioned before, in the companion paper [9], we use the findings from the current paper, to prove Conjecture 1 for 
all triangle-free graphs (with the same list of graphs requiring c > 0 when Δ ≥ 3). To do so, we will use Theorem 2 as the 
starting point of the proof. For Δ ≥ 3, the extremal triangle-free graphs (requiring c > 0) are actually the same extremal 
trees characterized in the current paper.
Declaration of competing interest
The authors declare that they have no known competing financial interests or personal relationships that could have 
appeared to influence the work reported in this paper.
Data availability
No data was used for the research described in the article.
References
[1] D. Archdeacon, J. Ellis-Monaghan, D. Fischer, D. Froncek, P.C.B. Lam, S. Seager, B. Wei, R. Yuster, Some remarks on domination, J. Graph Theory 46 
(2004) 207–210.
[2] D. Auger, Minimal identifying codes in trees and planar graphs with large girth, Eur. J. Comb. 31 (5) (2010) 1372–1384.
[3] L. Babai, On the complexity of canonical labeling of strongly regular graphs, SIAM J. Comput. 9 (1) (1980) 212–216.
[4] C. Balbuena, F. Foucaud, A. Hansberg, Locating-dominating sets and identifying codes in graphs of girth at least 5, Electron. J. Comb. 22 (2) (2015) P2.
[5] N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and locating-dominating codes on chains and cycles, Eur. J. Comb. 25 (7) (2004) 969–987.
[6] N. Bertrand, I. Charon, O. Hudry, A. Lobstein, 1-identifying codes on trees, Australas. J. Comb. 31 (2005) 21–36.
[7] M. Blidia, M. Chellali, F. Maffray, J. Moncel, A. Semri, Locating-domination and identifying codes in trees, Australas. J. Comb. 39 (2007) 219–232.
[8] J.A. Bondy, Induced subsets, J. Comb. Theory, Ser. B 12 (2) (1972) 201–202.
19 
D. Chakraborty, F. Foucaud, M.A. Henning et al. Discrete Mathematics 349 (2026) 114826 
[9] D. Chakraborty, F. Foucaud, M.A. Henning, T. Lehtilä, Identifying codes in triangle-free graphs of bounded maximum degree, arXiv preprint, arXiv:
2403.17877, 2024.
[10] D. Chakraborty, F. Foucaud, T. Lehtilä, Identifying codes in bipartite graphs of given maximum degree, Proc. Comput. Sci. 223 (2023) 157–165.
[11] E.-K. Cho, I. Choi, B. Park, On independent domination of regular graphs, J. Graph Theory 103 (2023) 159–170.
[12] E.-K. Cho, J. Kim, M. Kim, A. Oum, Independent domination of graphs with bounded maximum degree, J. Comb. Theory, Ser. B 158 (2023) 341–352.
[13] P. Dorbec, M.A. Henning, M. Montassier, J. Southey, Independent domination in cubic graphs, J. Graph Theory 80 (2015) 329–349.
[14] F. Foucaud, S. Gravier, R. Naserasr, A. Parreau, P. Valicov, Identifying codes in line graphs, J. Graph Theory 73 (4) (2013) 425–448.
[15] F. Foucaud, E. Guerrini, M. Kovše, R. Naserasr, A. Parreau, P. Valicov, Extremal graphs for the identifying code problem, Eur. J. Comb. 32 (4) (2011) 
628–638.
[16] F. Foucaud, R. Klasing, A. Kosowski, A. Raspaud, On the size of identifying codes in triangle-free graphs, Discrete Appl. Math. 160 (10–11) (2012) 
1532–1546.
[17] F. Foucaud, T. Lehtilä, Revisiting and improving upper bounds for identifying codes, SIAM J. Discrete Math. 36 (4) (2022) 2619–2634.
[18] F. Foucaud, G. Perarnau, Bounds for identifying codes in terms of degree parameters, Electron. J. Comb. 19 (1) (2012) 32.
[19] J. Gimbel, B. Van Gorden, M. Nicolescu, C. Umstead, N. Vaiana, Location with dominating sets, Congr. Numer. (2001) 129–144.
[20] W. Goddard, M.A. Henning, J. Lyle, J. Southey, On the independent domination number of regular graphs, Ann. Comb. 16 (2012) 719–732.
[21] W. Goddard, K. Wash, ID codes in Cartesian products of cliques, J. Comb. Math. Comb. Comput. 85 (2013) 97–106.
[22] S. Gravier, M. Kovše, M. Mollard, J. Moncel, A. Parreau, New results on variants of covering codes in Sierpin´ski graphs, Des. Codes Cryptogr. 69 (2) 
(2013) 181–188.
[23] S. Gravier, J. Moncel, On graphs having a V \{x} set as an identifying code, Discrete Math. 307 (3–5) (2007) 432–434.
[24] S. Gravier, J. Moncel, A. Semri, Identifying codes of cycles, Eur. J. Comb. 27 (5) (2006) 767–776.
[25] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (Eds.), Topics in Domination in Graphs, Developments in Mathematics, vol. 64, Springer, Cham, 2020.
[26] T.W. Haynes, S.T. Hedetniemi, M.A. Henning (Eds.), Structures of Domination in Graphs, Developments in Mathematics, vol. 66, Springer, Cham, 2021.
[27] T.W. Haynes, S.T. Hedetniemi, M.A. Henning, Domination in Graphs: Core Concepts, Springer Monographs in Mathematics, Springer, Cham, 2023.
[28] T.W. Haynes, M.A. Henning, J. Howard, Locating and total dominating sets in trees, Discrete Appl. Math. 154 (8) (2006) 1293–1300.
[29] M.A. Henning, A. Yeo, Total Domination in Graphs, Springer Monographs in Mathematics, Springer, Cham, 2013.
[30] M.A. Henning, A. Yeo, Total Domination in Graphs, Springer, 2013.
[31] D. Jean, A. Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs, https://dragazo.github.io/bibdom/main.pdf.
[32] V. Junnila, T. Laihonen, T. Lehtilä, On a conjecture regarding identification in Hamming graphs, Electron. J. Comb. (2019) P2.
[33] M.G. Karpovsky, K. Chakrabarty, L.B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inf. Theory 44 (2) (1998) 599–611.
[34] A. Kostochka, B. Stodolsky, An upper bound on the domination number of n-vertex connected cubic graphs, Discrete Math. 309 (5) (2009) 1142–1162.
[35] A. Lobstein, O. Hudry, I. Charon, Locating-domination and identification, in: Topics in Domination in Graphs, 2020, pp. 251–299.
[36] J. Moncel, On graphs on n vertices having an identifying code of cardinality [log2(n+1)], Discrete Appl. Math. 154 (14) (2006) 2032–2039.
[37] B.M.E. Moret, H.D. Shapiro, On minimizing a set of tests, SIAM J. Sci. Stat. Comput. 6 (4) (1985) 983–1003.
[38] O. Pikhurko, H. Veith, O. Verbitsky, The first order definability of graphs: upper bounds for quantifier depth, Discrete Appl. Math. 154 (17) (2006) 
2511–2529.
[39] H. Rahbani, N.J. Rad, S.M. Mirrezaei, Bounds on the identifying codes in trees, Graphs Comb. 35 (3) (2019) 599–609.
[40] D.F. Rall, K. Wash, Identifying codes of the direct product of two cliques, Eur. J. Comb. 36 (2014) 159–171.
[41] B. Reed, Paths, stars and the number three, Comb. Probab. Comput. 5 (3) (1996) 277–295.
[42] A. Rényi, On random generating elements of a finite Boolean algebra, Acta Sci. Math. Szeged. 22 (1961) 75–81.
[43] S. Thomassé, A. Yeo, Total domination of graphs and small transversals of hypergraphs, Combinatorica 27 (2007) 473–487.
[44] R. Ungrangsi, A. Trachtenberg, D. Starobinski, An implementation of indoor location detection systems based on identifying codes, in: F.A. Aagesen, C. 
Anutariya, V. Wuwongse (Eds.), Intelligence in Communication Systems, Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 175–189.
20