Previous work by Lesniak (1975) and recently by Qiao and Zhan (2022) established a sharp lower bound for the number of leaves of a tree as a function of its order and diameter. In this note, we derive a lower bound for the number of leaves as a function of the entire sequence of eccentricities, and provide a complete characterisation of all trees attaining equality. We also obtain a new but simpler proof for the diameter-bound. Furthermore, we establish the analogous result for the maximum with respect to the entire eccentric sequence.
In extremal graph theory, one usually investigates the maximum and minimum values of a chosen structural parameter in graphs sharing a given set of constraints. For example, Turán’s Theorem [18] states that among all graphs with \(n\) vertices not containing a clique of size \(p\), the complete \((p-1)\)-partite graph with as nearly equal as possible parts has the maximum number of edges. Let \(G\) be a simple connected graph and \(V(G)\) its vertex set. The eccentricity, denoted by \({\rm ec}_{G}(v)\), of \(v\in V(G)\) is defined as the maximum distance from \(v\) to any other vertex of \(G\). Eccentricity is an important and well-studied concept in graph theory. For example, in transportation networks eccentricity is an indicator of the worst-case travel time starting at a given vertex. We are interested in the multiset of eccentricities of \(G\). Thus, a sequence \(S=(b_1^{(m_1)},b_2^{(m_2)},\ldots, b_l^{(m_l)})\) in which \(b_1,b_2,\ldots,b_l\) appears exactly \(m_1,m_2,\ldots,m_l\) times, respectively, and \(b_1<b_2<\cdots <b_l\), is called an eccentric sequence of a graph (resp. a tree eccentric sequence) if there is a graph \(G\) (resp. a tree \(T\)) with \(m_1+m_2+\cdots +m_l\) vertices of which precisely \(m_j\) have eccentricity \(b_j\) in \(G\) (resp. in \(T\)) for all \(1\leq j \leq l\).
The study of eccentric sequences started in 1975 with Lesniak [13]. It is difficult, in general, to decide whether a given sequence is the eccentric sequence of some graph. Lesniak [13] gave a necessary condition for a sequence of nonnegative integers to be eccentric. A sequence \(S'\) obtained from \(S\) by omitting (possibly none) some entries of \(S\) in such a way that \(S\) and \(S'\) have the same number of distinct entries, is called a subsequence of \(S\). In [13], Lesniak proved that \(S\) is eccentric if and only if \(S\) has a subsequence that is also eccentric. However, this characterisation cannot always be used to test if a given sequence is eccentric, since \(S\) itself may have no proper eccentric subsequence. Naturally, the concept of minimal eccentric sequences arises; it is defined as those sequences that have no proper eccentric subsequence. Minimal eccentric sequences were studied in Nandakumar’s PhD thesis [15] and later by other researchers [10, 11, 12] in few special cases. It should be noted that this approach to characterising eccentric sequences has not succeeded yet since no good characterisation of minimal eccentric sequences has been found yet [2].
Lesniak [13] further narrowed down to trees, and provided the characterisation given in Theorem 1.1 below. An equivalent statement was also given independently by Behzad and Simpson [1].
Theorem 1.1([1, 13]).A sequence \(S=(b_1^{(m_1)},b_2^{(m_2)},\ldots, b_l^{(m_l)})\) is a tree eccentric sequence if and only if
i) \(b_{j+1}=b_j +1\) for all \(1\leq j \leq l-1\), \(m_2,\ldots,m_l>1\),
ii) \(m_1=1\) and \(b_l=2b_1\), or \(m_1=2\) and \(b_l=2b_1-1\).
Theorem 1.1 suggests that the eccentric sequence of any connected graph is ‘dominated’ by that of a path, when both graphs have the same order; see [3]. To the best of our knowledge, besides trees, maximal outerplanar graphs (triangulations of polygons) are the only non-trivial graph class for which a full characterisation of eccentric sequences, similar to Theorem 1.1, was obtained [6]. Therefore, characterising all eccentric sequences remains an elusive task. On the other hand, some studies have been done by Gimbert and Lopez [9] on the eccentric sequences of strongly connected digraphs.
In a recent paper [4] the present authors characterised trees with a given eccentric sequence that have the minimum Wiener index (sum of distances between all unordered pairs of vertices) or the maximum number of subtrees. In [5] the results were extended to the \(k\)-Steiner Wiener index and a class of Wiener-type indices that includes the hyper- and generalised Wiener indices, and the Harary index, among others. In this note, we are interested in a similar extremal problem in trees, using the eccentric sequence to bound the number of leaves, and also characterise all extremal structures.
The set of leaves of a tree \(T\) will be denoted by \(L(T)\). If \(S\) is a tree eccentric sequence, then we denote by \(\mathcal{T}_S\) the set of all trees whose eccentric sequence is \(S\).
A caterpillar is a tree with the property that deleting all leaves yields a path. In particular, every path is a caterpillar.
Proposition 2.1([13, 17]).For every tree eccentric sequence \(S\), there is a caterpillar whose eccentric sequence is \(S\).
We mention that Skurnik [17] determined the exact number of nonisomorphic caterpillars whose eccentric sequence is \(S\).
The diameter, \({\rm diam}(G)\), of a connected graph \(G\) is the largest entry in its eccentric sequence, while the radius, \({\rm rad}(G)\), is the smallest eccentricity among the vertices of \(G\). It is a standard fact that all vertices of eccentricity \({\rm diam}(T)\) are leaves in a tree \(T\), since otherwise, a path of length longer than \({\rm diam}(T)\) can be obtained in \(T\).
We show – not unexpectedly – that only caterpillars have the maximum number of leaves among all trees with a given eccentric sequence or a given diameter.
Theorem 2.2. Let \(S=(b_1^{(m_1)},b_2^{(m_2)},\ldots, b_l^{(m_l)})\) be a tree eccentric sequence and \(T\in \mathcal{T}_S\). Then \[|L(T)|\leq m_1+m_2+\cdots +m_l-b_l+1\,.\] Equality holds if and only if \(T\) is a caterpillar.
Proof. Fix a longest path \(P\) in \(T\). An internal vertex of \(P\) is not a leaf of \(T\). Since \(P\) has \(b_l-1\) internal vertices, we deduce that \(T\) has at most \[m_1+m_2+\cdots +m_l+1-b_l,\] leaves. Equality holds if and only if every element of \(V(T)\smallsetminus V(P)\) is adjacent to exactly one vertex of \(P\). In this case, \(T\) is a caterpillar. On the other hand, if \(T\) is a caterpillar, then clearly equality holds in Theorem 2.2. ◻
By Proposition 2.1, every tree eccentric sequence is realised by some caterpillar. Thus, the bound in Theorem 2.2 is sharp for every tree eccentric sequence. In particular, we recover the following well-known result:
Corollary 2.3. Let \(d,n\) be integers such that \(1\leq d \leq n-1\), and \(T\) a tree with \(n\) vertices and diameter \(d\). Then \(|L(T)|\leq n-d+1\), with equality if and only if \(T\) is a caterpillar.
The problem of determining the possible number of leaves in a tree of given order and diameter was first investigated by Lesniak [14]. The lower bound given in [14] is sharp only when the diameter is even. Later, Qiao and Zhan [16] filled this gap by computing the number of leaves of so-called spiders (subdivision of stars) and by transforming any tree \(T\) to a spider with the same order, diameter and number of leaves as \(T\). Nevertheless, the cases of equality were not derived. Very recently, in their note [8], Feng and Huang generalised the ideas [14, 16] by determining the numbers of leaves as a function of order, diameter and maximum degree of a tree, but they did not construct all the extremal structures.
In what follows, we assume that \(S=(b_1^{(m_1)},b_2^{(m_2)},\ldots, b_l^{(m_l)})\) is a fixed tree eccentric sequence, and we denote \(m_1 + \cdots + m_l\) by \(n\), so \(n\) is the order of a tree with eccentric sequence \(S\). Henceforth, also assume \(n>2\). As usual, the \(m\)-vertex path is denoted by \(P_m\).
For our next theorem which describes trees with eccentric sequence \(S\) and the minimum number of leaves, we introduce \(\bullet\) as follows: \[\begin{aligned} a \bullet b=\left\{ \begin{array}{rcl} 0 & \mbox{if} & a\leq b \\ a-b & \mbox{if} & a>b\, \end{array}\right. = \max(a-b,0) \quad \text{for any real numbers $a,b$}\,. \end{aligned}\]
In the proof of Lemma 2.5 we make use of the following result in [7] (see the proof of Theorem 2 there).
Proposition 2.4 ([7]).Let \(T\) be a tree and \(C(T)\) the centre (set of vertices with the minimum eccentricity) of \(T\). Then \[{\rm ec}_T(x) = d_T(x,C(T))+ {\rm rad}(T),\] for all vertices \(x\) of \(T\).
By a diametral path in a tree \(T\), we mean any longest path (thus of length \({\rm diam}(T)\)). Recall that the two endvertices of such a path are necessarily leaves in \(T\). We refer to such an endvertex as a diametral vertex.
Lemma 2.5. Let \(T\) be a tree on at least three vertices, and let \(T'\) be obtained from \(T\) by removing all vertices of eccentricity \({\rm diam}(T)\). Then \[{\rm ec}_{T'}(x) = {\rm ec}_{T}(x)-1,\] for all vertices \(x\) of \(T'\).
Proof. For simplicity, denote the radius and diameter of \(T\) by \(r\) and \(d\), respectively. Let \(V_d\) be the set of vertices of \(T\) whose eccentricity equals \(d\). So \(T'= T-V_d\). Let \(x \in V(T)-V_d\) be an arbitrary vertex. Since the vertices in \(V_d\) are leaves, and since removing leaves cannot decrease the eccentricity of a vertex by more than \(1\), we have \({\rm ec}_{T'}(x) \geq {\rm ec}_{T}(x)-1\). Hence we only have to show that \({\rm ec}_{T'}(x) \leq {\rm ec}_{T}(x)-1\). We consider two cases.
Case 1. \(d=2r\).
Then \(C(T)\) consists of a single vertex, \(c\) say. It follows from Proposition 2.4 that \(V_d\) consists of those vertices of \(T\) that are at distance \(r\) from \(c\). Therefore, \({\rm ec}_{T'}(c) =r-1\), and so \[{\rm ec}_{T'}(x) \leq d_{T'}(x,c) + {\rm ec}_{T'}(c) = d_{T}(x,c) + {\rm ec}_{T}(c) – 1 = {\rm ec}_{T}(x) -1,\] as desired.
Case 2. \(d=2r-1\).
Then \(C(T)\) consists of two adjacent vertices, \(c_1\) and \(c_2\) say. It follows from Proposition 2.4 that \(V_d\) consists of those vertices that are at distance \(r-1\) from the nearest vertex in \(\{c_1, c_2\}\). Therefore, in \(T'\) every vertex is within distance \(r-2\) of \(\{c_1,c_2\}\), and so \({\rm ec}_{T'}(c_i) \leq r-1\) for \(i=1,2\). If \(c_j\) is the centre vertex closest to \(x\), we thus have \[{\rm ec}_{T'}(x) \leq d_{T'}(x,c_j) + {\rm ec}_{T'}(c_j) \leq d_{T}(x,C(T)) + r – 1 = {\rm ec}_{T}(x) -1,\] as desired. ◻
Our next task is to set a constructive procedure that yields certain tree families.
Definition 2.6. Starting from an initial tree eccentric sequence \(U=(a_1^{(m_1)},a_2^{(m_2)},\ldots, a_t^{(m_t)})\), denote by \(\mathcal{F}_{m_t}[U]\) the family of all trees with this eccentric sequence. Recall that all \(m_t\) vertices of eccentricity \(a_t\) are leaves.
i) Let us be given integers \(m_{t+1}, m_{t+2}, \ldots, m_{t+k}>1\) for some integer \(k\geq 1\). Suppose that the tree families \(\mathcal{F}_{m_t,\ldots,m_{t+j}}[U]\), \(j=0,\ldots,k-1\) have been constructed, and that there are precisely \(m_{t+j}\) vertices of eccentricity \(a_{t+j}:=a_t+2j\) in any element of \(\mathcal{F}_{m_t,\ldots,m_{t+j}}[U]\), all of which are leaves.
ii) Then \(\mathcal{F}_{m_t,m_{t+1},\ldots,m_{t+k}}[U]\) consists of all trees \(T_{t+k}\) obtained as follows:
Take a tree \(T_{t+k-1} \in \mathcal{F}_{m_t, \ldots,m_{t+k-1}}[U]\).
If \(m_{t+k}>m_{t+k-1}\) then attach a total of \(m_{t+k}\) pendant edges to the \(m_{t+k-1}\) vertices (leaves) of eccentricity \(a_{t+k-1}\) in \(T_{t+k-1}\) in such a way that each of these \(m_{t+k-1}\) leaves of \(T_{t+k-1}\) is assigned to at least one pendant edge. Note that we have destroyed \(m_{t+k-1}\) leaves of \(T_{t+k-1}\) and added \(m_{t+k}\) new leaves to obtain the tree \(T_{t+k}\).
If \(m_{t+k}\leq m_{t+k-1}\) then pick \(m_{t+k}\) vertices (leaves) including at least two at distance \(a_{t+k-1}\), among the \(m_{t+k-1}\) leaves of eccentricity \(a_{t+k-1}\) in \(T_{t+k-1}\), and attach one pendant edge to each of them. Note that we have destroyed \(m_{t+k}\) leaves of \(T_{t+k-1}\) and added \(m_{t+k}\) new leaves to obtain the tree \(T_{t+k}\).
The lemma below supports Definition 2.6.
Lemma 2.7. All trees \(T_{t+k} \in \mathcal{F}_{m_t,\ldots,m_{t+k}}[U]\) have eccentric sequence \[\begin{aligned} \label{FORM} U_{t+k}:=&\bigg((a_1+k)^{(m_1)},\ldots, (a_t+k)^{(m_t)}, \nonumber\\ & (a_t+k+1)^{(m_{t+1})},\ldots, (a_t+2k-1)^{(m_{t+k-1})}, (a_t+2k)^{(m_{t+k})} \bigg)\,. \end{aligned} \tag{1}\]
In particular, the \(m_{t+j}\) vertices of eccentricity \(a_{t+j}=a_t+2j\) in any element of \(\mathcal{F}_{m_t,\ldots,m_{t+j}}[U]\) are indeed leaves.
Proof. The sequence \(U_t:=(a_1^{(m_1)},a_2^{(m_2)},\ldots, a_t^{(m_t)})=U\) is the eccentric sequence of every \(T_{t} \in \mathcal{F}_{m_t}[U]\), so the base case \(k=0\) holds.
Let \(u, v\) be two vertices at the maximum distance (the path between \(u\) and \(v\) is diametral) in a tree \(T\). It is well known that \[\begin{aligned} {\rm ec}_{T}(w)=\max\{d_T(w,u), d_T(w,v) , \} \end{aligned}\] holds for any vertex \(w\) of \(T\); see [4, 13].
We continue by induction on \(k\). Let \(k\geq 1\), and assume \(m_{t+k}>1\) is given and that every \(T_{t+j} \in \mathcal{F}_{m_t,\ldots,m_{t+j}}[U]\) have eccentric sequence \(U_{t+j}\) for all \(j=0,1,\ldots,k-1\). Consider a tree \(T_{t+k} \in \mathcal{F}_{m_t,\ldots,m_{t+k}}[U]\). We employ both Definition 2.6 and Lemma 2.7, without further reference.
Case 1. \(m_{t+k}\leq m_{t+k-1}\).
By construction of \(T_{t+k}\), there are at least two vertices, say \(u,v\), at distance \({\rm diam} (T_{t+k-1})\), among the chosen \(m_{t+k}\) leaves of eccentricity \(a_{t+k-1}=a_t+2(k-1)\) in \(T_{t+k-1}\). Denote by \(R\) the set of all these \(m_{t+k}\) chosen leaves of \(T_{t+k-1}\). Since each element (including \(u\) and \(v\)) of \(R\) is now incident with a new pendant edge in \(T_{t+k}\), we have \[\begin{aligned} {\rm ec}_{T_{t+k-1}}(w)=\max \{d_{T_{t+k-1}}(w,u), d_{T_{t+k-1}}(w,v) \} \quad \text{for all}\quad w \in V(T_{t+k-1})\,, \end{aligned}\] which implies that \[\begin{aligned} {\rm ec}_{T_{t+k}}(w)=1+{\rm ec}_{T_{t+k-1}}(w)=1+a_{t+k-1} \quad \text{for all} \quad w \in V(T_{t+k-1}), \end{aligned}\] and that \[\begin{aligned} {\rm ec}_{T_{t+k}}(x)=2+ a_{t+k-1} \quad \text{for all} \quad x \in V(T_{t+k})\backslash V(T_{t+k-1})\,. \end{aligned}\]
Therefore, the eccentric sequence of \(T_{t+k}\) is \[\begin{aligned} &\big((a_1+k-1+1)^{(m_1)},\ldots, (a_t+k-1+1)^{(m_t)}, (a_t+k+1)^{(m_{t+1})},\ldots,\\ & (a_t+2k-3+1)^{(m_{t+k-2})}, (a_t+2k-2+1)^{(m_{t+k-1})}, (2+a_{t+k-1})^{m_{t+k}} \big)\\ &=\big((a_1+k)^{(m_1)},\ldots, (a_t+k)^{(m_t)}, (a_t+k+1)^{(m_{t+1})},\ldots,\\& (a_t+2k-1)^{(m_{t+k-1})}, (a_t+2k)^{(m_{t+k})}\big)\\ &=U_{t+k}\,. \end{aligned}\]
Case 2: \(m_{t+k}> m_{t+k-1}\).
By construction of \(T_{t+k}\), every diametral vertex of \(T_{t+k-1}\) is now incident with at least one new pendant edge in \(T_{t+k}\). An argument analogous to Case 1 gives us \[\begin{aligned} & {\rm ec}_{T_{t+k}}(w)=1+{\rm ec}_{T_{t+k-1}}(w)=1+a_{t+k-1} \quad \text{for all} \quad w \in V(T_{t+k-1})\,,\\ &{\rm ec}_{T_{t+k}}(x)=2+ a_{t+k-1} \quad \text{for all} \quad x \in V(T_{t+k})\backslash V(T_{t+k-1})\,, \end{aligned}\] proving that \(U_{t+k}\) is indeed the eccentric sequence of \(T_{t+k}\).
This completes the proof of (1) as well as the lemma. ◻
In particular, for every \(k\geq 1\), we always destroy exactly \(\min\{m_{t+k}, m_{t+k-1}\}\) leaves in \(T_{t+k-1}\) when moving from \(T_{t+k-1}\) to the tree \(T_{t+k}\); see Definition 2.6.
Below we give some illustrations of the family \(\mathcal{F}_{m_t,\ldots,m_{t+k}}[U]\).
Example 2.8.Let \(U=(1^{(m_1)}, 2^{(m_2)})\). Then \(t=2\), \(m_2>1\) and \(m_1=1\). So \(\mathcal{F}_{m_2}[U]\) consists only of the star \(T_2\) on \(m_2\) leaves. Let us take \(m_2=3\).
Step \(k=1\). Let us take \(m_3=5\). Since \(m_3>m_2\), the family \(\mathcal{F}_{m_2,m_3}[U]\) can only consist (up to isomorphism) of the two trees below:
Step \(k=2\). Let us take \(m_4=2\). We choose the leftmost tree in Figure 1 to be \(T_3\), and construct a \(T_4\) as shown below:
Example 2.9. Let \(U=(2^{(m_1)}, 3^{(m_2)})\). Then \(t=2\), \(m_2>1\) and \(m_1=2\). The family \(\mathcal{F}_{m_2}[U]\) can only consist (up to isomorphism) of all double stars (an edge \(uv\) with only leaves attached to \(u\) and to \(v\)) on \(m_2\) leaves; see below for an example with \(m_2=6\).
Step \(k=1\). Let us take \(m_3=2\). Starting from the tree in Figure 3 and given that \(m_3 < m_2\), we choose to construct the tree shown below:
Step \(k=2\). Let us take \(m_4=2\). Starting from the tree in Figure 4, we necessarily obtain the tree shown below:
Any tree eccentric sequence \(S=(b_1^{(m_1)},b_2^{(m_2)},\ldots, b_l^{(m_l)})\) always admits the form (1); see Theorem 1.1. We can now state and prove our next theorem.
Here and in the following, empty sums should be treated as zero.
Theorem 2.10. Let \(T\in \mathcal{T}_S\). Then \[\begin{aligned} \label{3A} |L(T)|\geq m_2+\sum_{j=2}^{l-1} m_{j+1} \bullet m_j\,. \end{aligned} \tag{2}\]
Equality holds if and only if \[\begin{aligned} T\in \mathcal{F}_{{m_2,\ldots,m_l}}[1^{(m_1)},2^{(m_2)}] \quad \text{for}~~ b_l ~~ \text{even, and} ~~ T\in \mathcal{F}_{{m_2,\ldots,m_l}}[2^{(m_1)},3^{(m_2)}] \quad \text{for}~~ b_l~~ \text{odd}\,. \end{aligned}\]
Proof. We prove the bound by induction on the diameter of \(T\). If \(b_l\in\{2,3\}\) then \(l=2\) and the theorem clearly holds with equality. The tree families in this case are \(\mathcal{F}_{{m_2}}[1^{(m_1)},2^{(m_2)}]\) for \(b_l=b_2=2\), and \(\mathcal{F}_{{m_2}}[2^{(m_1)},3^{(m_2)}]\) for \(b_l=b_2=3\).
Now assume that \(b_l>3\) (thus \(l>2\)) and let \(T'\) be obtained from \(T\) by deleting all vertices (leaves) of eccentricity \(b_l\). By Lemma 2.5, the eccentric sequence of the tree \(T'\) is \[\big( (b_1-1)^{(m_1)}, (b_2-1)^{(m_2)}, \ldots, (b_{l-1}-1)^{(m_{l-1})}\big)\,,\] and the induction hypothesis applied to \(T'\) yields \[\begin{aligned} \label{BoundT'} |L(T')|\geq m_2+\sum_{j=2}^{l-2} m_{j+1} \bullet m_j\,. \end{aligned} \tag{3}\]
Since the \(m_l\) vertices of eccentricity \(b_l\) in \(T\) are leaves, they are necessarily adjacent to vertices \(v\) of eccentricity \(b_{l-1}=b_l-1\) in \(T\). Any such vertex \(v\) is now of eccentricity \(b_{l-1}-1\) in \(T'\) (see Lemma 2.5), which is the diameter of \(T'\). Thus, any such \(v\) is a leaf in \(T'\). Consequently, adding back these \(m_l\) leaves to \(T'\) to obtain \(T\) can only destroy a subset of diametral vertices (leaves) of \(T'\) that definitely comprises at least two leaves at distance \({\rm diam}(T')\). If \(m_l\leq m_{l-1}\), then adding back these \(m_l\) leaves to \(T'\) to obtain \(T\) can only destroy at most \(m_l\) diametral vertices (leaves) of \(T'\). In any case, the addition of the \(m_l\) leaves to \(T'\) can only destroy at most \(\min \{m_{l-1},m_l\}\) leaves of the tree \(T'\). This gives us \[\begin{aligned} \label{BoundT} |L(T)|& \geq |L(T')|+ m_l-\min \{m_{l-1},m_l\} =|L(T')|+(m_{l} \bullet m_{l-1}) \nonumber\\ &\geq m_2+\sum_{j=2}^{l-1} m_{j+1} \bullet m_j\,, \end{aligned} \tag{4}\] which proves (2). Moreover, equality holds in (4) if and only if it holds in (3) and that precisely \(\min \{m_{l-1},m_l\}\) diametral vertices (leaves, including at least two at distance \({\rm diam}(T')\)) are destroyed in \(T'\) when adding back the \(m_l\) leaves to \(T'\). In other words, equality in (2) forces both equality in each induction step and the destruction of precisely \(\min \{m_{l-1},m_l\}\) diametral vertices (including at least two leaves at distance diameter) in the current tree, and therefore the recursive structure of Definition 2.6.
For sufficiency, we need to show that every tree \(T_l\in \mathcal{F}_{{m_2,\ldots,m_l}}[1^{(m_1)},2^{(m_2)}]\) for \(b_l\) even, and every \(T_l\in \mathcal{F}_{{m_2,\ldots,m_l}}[2^{(m_1)},3^{(m_2)}]\) for \(b_l\) odd, realises equality in (2).
Consider the base cases: \(\mathcal{F}_{m_2}[1^{(m_1)},2^{(m_2)}]\) consists only of the star \(T_2\) on \(m_2\) leaves, and \(\mathcal{F}_{m_2}[2^{(m_1)},3^{(m_2)}]\) consists of all double stars \(T_2\) on \(m_2\) leaves; this agrees with equality in (2). With Definition 2.6 at hand, we have \[\begin{aligned} |L(T_{t+k})|=|L(T_{t+k-1})|-\min \{m_{t+k},m_{t+k-1}\} +m_{t+k}, \end{aligned}\] for all \(k\geq 1\). Through iteration on \(k\), we obtain \[\begin{aligned} |L(T_{t+k})|=|L(T_{t+0})|+ \sum_{j=1}^{k} (m_{t+j} – \min \{m_{t+j},m_{t+j-1}\} )=|L(T_{t+0})|+ \sum_{j=1}^{k} m_{t+j} \bullet m_{t+j-1} \,, \end{aligned}\] which implies that \[\begin{aligned} &|L(T_{2+k})|=|L(T_{2+0})|+ \sum_{j=1}^{k} m_{2+j} \bullet m_{2+j-1} = m_2 + \sum_{i=0}^{k-1} m_{i+3} \bullet m_{2+i} \,,\\ & |L(T_{2+(l-2)})|= m_2 + \sum_{i=0}^{l-3} m_{i+3} \bullet m_{2+i}=m_2 + \sum_{j=2}^{l-1} m_{j+1} \bullet m_{j}\,. \end{aligned}\]
Since \(T\) is a certain \(T_l\), the proof of the theorem is finished. ◻
As an immediate corollary to the above theorem, we obtain:
Corollary 2.11. For a tree \(T\), it holds that \[|L(T)| \geq \max \{m_2,m_3,m_4\}\,,\] where \(m_j\) is the number of vertices of eccentricity \({\rm rad}(T)+j-1\) in \(T\).
Proof. We employ (2). By definition, \(a \bullet b\geq 0\) for all real \(a,b\). Thus \(|L(T)| \geq m_2\).
If \(m_3\geq m_2\), then \(|L(T)| \geq m_2 + (m_3-m_2)=m_3\). If \(m_3\leq m_2\), then \(|L(T)| \geq m_2 + (m_4-m_3) =m_4+ (m_2-m_3)\geq m_4\). Hence, the corollary follows. ◻
Upon refining the ideas in our proof, one obtains:
Theorem 2.12. Let \(d,n\) be integers such that \(2 \leq d \leq n-1\), and \(T\) a tree with \(n\) vertices and diameter \(d\). Then \[\begin{aligned} \label{minleafDiam} |L(T)|\geq 2+ \Big\lceil \frac{n-d-1}{\lfloor d/2 \rfloor} \Big\rceil\,. \end{aligned} \tag{5}\]
Equality is attained, for example, if \(T\) can be obtained from \(P_{d+1}\) by taking additional \(\lceil \frac{n-d-1}{\lfloor d/2 \rfloor} \rceil\) disjoint paths, each of length at most \(\lfloor d/2 \rfloor\), and identifying one endvertex of each of these paths with the same centre vertex of \(P_{d+1}\).
Proof. If \(T\) is a path, there is nothing to prove. Otherwise, fix a longest (thus diametral) path \(P\) in \(T\) with endvertices \(u_1, u_2\) (thus leaves in \(T\)), and let \(v \in V(T) \smallsetminus V(P)\). Suppose that \[\min \{d_T(v, w):~ w\in V(P)\} > d/2 \,.\]
Since \(d_T(v,u_1)=d_T(v,v')+d_T(v',u_1)\) and \[\begin{aligned} d_T(v,u_2)=d_T(v,v')+d_T(v',u_2)=d_T(v,v')+d – d_T(v',u_1)\,, \end{aligned}\] where \(v' \in V(P)\) is any fixed vertex that realises \(\min \{d_T(v, w):~ w\in V(P)\}\), we have \[\begin{aligned} & d_T(v,u_1) > d/2 + d/2 \quad \text{if} \quad d_T(v',u_1) \geq d/2 \,,\\ & \text{and} \quad d_T(v,u_2)> d/2 + d – d/2 \quad \text{if} \quad d_T(v',u_1) \leq d/2 \,. \end{aligned}\]
In any case, either \(d_T(v,u_1) > d\) or \(d_T(v,u_2)>d\). In particular, we obtain a contradiction on the diameter \(d\) of the tree \(T\). Hence, \(\min \{d_T(v, w):~ w\in V(P)\} \leq d/2\) holds.
Denote by \(u_3, u_4, \ldots, u_l\) all the leaves of \(T\) not on the path \(P\), and by \(d_j\) the minimum distance from \(u_j\) to a vertex of \(P\), for \(j=3,~4,~\ldots,~l\). Thus, there are \(d_j\) vertices not on \(P\) and belonging to the path from \(u_j\) to the nearest vertex of \(P\). Since there are only \(n-d-1\) vertices of \(T\) not on \(P\), we deduce that \[\begin{aligned} \label{low:Diam} d_3+d_4+\cdots +d_l\geq n-d-1\,. \end{aligned} \tag{6}\]
Equality holds in (6) if and only if all paths from \(u_j\) to their respective nearest vertices on \(P\) are pairwise vertex disjoint, except possibly that they may have common vertex on \(P\). On the other hand, \[\begin{aligned} \label{upp:Diam} d_j \leq \lfloor d/2 \rfloor \quad \text{for all}~~ j, \end{aligned} \tag{7}\] implies that \(d_3+d_4+\cdots +d_l\leq (l-2) \lfloor d/2 \rfloor\). From these two inequalities, we infer \[\begin{aligned} \label{ALL:Diam} n-d-1 \leq (l-2) \lfloor d/2 \rfloor\,, \end{aligned} \tag{8}\] thus the bound (5) in the theorem.
Equality holds in (8) if and only if it holds in both (6) and (7). However, because of the ceiling function that appears in (5), it is no longer necessary to have equality in (6) and (7) in order to achieve equality in (5). For example, the tree obtained from \(P_{d+1}\) by taking additional \(\lceil \frac{n-d-1}{\lfloor d/2 \rfloor} \rceil\) disjoint paths, each of length at most \(\lfloor d/2 \rfloor\), and identifying one endvertex of each of these paths with the same centre vertex of \(P_{d+1}\), reaches the bound in (5). This proves the theorem. ◻
We recall that the bound in Theorem 2.12 was previously derived through several steps by Qiaoa and Zhan [16], with the characterisation of only one equality instance. Here we have implicitly characterised several cases of equality; see the discussion from the last paragraph in the proof of Theorem 2.12 together with Figures 6 and 7.
For example, in the case where \(d\) is odd, there are generally at least \[\begin{aligned} 1+ \Big \lfloor \frac{\big\lceil \frac{n-d-1}{\lfloor d/2 \rfloor} \big\rceil }{2} \Big \rfloor, \end{aligned}\] nonisomorphic trees of the shape depicted in Figure 6 (depending on how many ‘legs’ are attached to each of the two centre vertices), all of which attain the bound (5).
For general \(d\), it is possible to obtain other extremal shapes in which ‘legs’ are not necessarily internal disjoint, if one exploits carefully the residu class of \(n-d-1\) modulo \(\lfloor d/2 \rfloor\). We omit the details. It is therefore natural to ask:
Question 2.13. Can we constructively characterise all tree structures achieving the bound in Theorem 2.12 ? Is so, how many are there?
The authors have no conflicts of interests to declare.