An (unrooted) binary tree is a tree in which every internal vertex has degree \(3\). In this paper, we determine the minimum and maximum number of total dominating sets in binary trees of a given order. The corresponding extremal binary trees are characterized as well. The minimum is always attained by the binary caterpillar, while the binary trees that attain the maximum are only unique when the number of vertices is not divisible by~\(4\). Moreover, we obtain a lower bound on the number of total dominating sets for \(d\)-ary trees and characterize the extremal trees as well.
A dominating set \(D\) is a set of vertices in a graph \(G\) such that every vertex that is not in \(D\) has a neighbour in \(D\). The set \(D\) is a total dominating set (abbreviated as TDS) if every vertex has a neighbour in \(D\), whether it lies in \(D\) or not. For a thorough review of total domination, see the book by Henning and Yeo [9]. Krzywkowski and Wagner [11] studied the number of TDS (henceforth denoted by \(\delta_t(G)\)) in a graph \(G\). The trivial bounds on the number of TDS in a graph with \(n\) vertices are \(0 \leq \delta_t(G)\leq 2^n-n-1\). Here, the lower bound holds with equality if and only if \(G\) has one or more isolated vertices (in this case, \(G\) does not have any TDS). The upper bound holds with equality if and only if \(G\) is a complete graph. For a tree \(T\) with \(n\) vertices, \(\delta_t(T)\leq 2^{n-1}-1\), with equality for the star. The lower bound for trees is of order \(\Theta (9^{\frac{n}{7}})\). The extremal trees are obtained as unions of subdivided stars, and they are generally not unique. Krzywkowski and Wagner also obtained a sharp lower bound on \(\delta_t(T)\) including both the order and the total domination number and characterized the extremal graphs. Haynes and Henning [6] considered trees with unique minimum TDS, see also Henning [7]. There are also similar results on dominating sets [3,13,15], minimal dominating sets [4,10] and minimal TDS [1,5,8].
A vertex of a tree that has exactly one neighbour is a leaf; otherwise, it is called an internal vertex. A binary tree (more precisely, unrooted binary tree) is a tree in which all internal vertices are exactly of degree \(3\) (see for instance [14]). Such trees arise for example in the context of phylogenetics. More generally, if all internal vertices of a tree are exactly of degree \(d+1\), it is known as a \(d\)-ary tree. It is easy to see that a \(d\)-ary tree with \(k\) internal vertices has \(k (d-1)+2\) leaves, thus \(kd+2\) vertices in total.
A rooted binary tree has a distinguished root of degree \(2\), while all other internal vertices have degree \(3\). Here and in the following, whenever we only write “binary tree” without further specification, we refer to unrooted binary trees.
This paper focuses on the number of TDS in binary trees, specifically on the maximum and minimum number of TDS in binary trees of a given order. Similar results have been obtained for the number of subtrees [14], the number of independent sets and the number of matchings [2] in binary trees. See also [12] for analogous results on the number of (not necessarily total) dominating sets.
In the following section, we will show that the minimum number of TDS of a \(d\)-ary tree with \(k\) internal vertices is \(2^{k(d-1)+2}\). This minimum is attained by the binary caterpillar for binary trees (a binary caterpillar is a binary tree in which the internal vertices form a path), while for \(d >2\) there are generally many \(d\)-ary trees that attain the minimum (see Theorem 2.1). Also, for \(k\geq 4\), the second smallest possible number of TDS in a binary tree is \(25 \cdot 2^{k-2}\), and the binary trees that attain this value can also be characterized (Theorem 2.4). Lastly, the binary trees with maximum number of TDS are established in Theorem 3.7 and Theorem 3.8. In the case where the number of internal vertices is even (thus the total number of vertices is \(\equiv 2 \mod 4\)), there is always a unique tree attaining the maximum, while there is a family of trees attaining the maximum if the number of internal vertices is odd.
As a first result, we obtain the minimum number of TDS in \(d\)-ary trees and characterize the extremal cases. The precise statement reads as follows.
Theorem 2.1. For every \(d\)-ary tree \(T\) with \(k\geq2\) internal vertices, we have \[\delta_t(T)\geq 2^{k(d-1)+2}.\] Strict inequality holds if and only if there is a vertex of degree \(d+1\) in the tree induced by the internal vertices of \(T\) (equivalently, if there is an internal vertex that is not adjacent to a leaf).
Proof. Recall that \(T\) has \(k(d-1)+2\) leaves. The set of all internal vertices in \(T\) is a TDS of \(T\), and any subset of leaves can be added to this set. So we always have (at least) \(2^{k(d-1)+2}\) TDS. Let \(T'\) be the tree formed by the internal vertices of \(T\), and suppose first that \(T'\) does not have a vertex of degree \(d+1\). Then every vertex in \(T'\) has degree at most \(d\) and must therefore be adjacent to a leaf in \(T\). This implies that every internal vertex in \(T\) must be included in every TDS of \(T\), which readily proves that \(\delta_t(T) = 2^{k(d-1)+2}\).
Conversely, suppose that there is a vertex \(v\) of degree \(d+1\) in \(T'\). Then \(v\) has no leaf neighbour in \(T\). Now the set that consists of all vertices in \(T\) except for \(v\) is a TDS of \(T\) that has not been counted before, showing that strict inequality holds. ◻
For \(d=2\), the condition that the tree induced by the internal vertices has no vertex of degree \(3\) is equivalent to this tree being a path. In this case, \(T\) must be a binary caterpillar. So we have the following corollary.
Corollary 2.2. The binary caterpillar is the unique tree with the minimum number of TDS among all binary trees of a given order.
By contrast, for \(d > 2\), there are generally many trees of a given order that attain the minimum.
Next we determine the binary trees with the second smallest number of TDS. Let us start with some terminology. An internal vertex that is adjacent to at least one leaf is called a support vertex. Otherwise, we call it a leafless vertex. We will repeatedly make use of the fact that every TDS has to contain all support vertices of a tree (since they are required to totally dominate their leaf neighbours). A broom \(B(n,m)\) is a tree with \(n\) vertices that consists of a path with \(m\) vertices and \(n-m\) leaves that are all adjacent to one leaf of the path.
Lemma 2.3. Let \(T\) be a binary tree with exactly one leafless vertex and \(k\geq 5\) internal vertices in total. Then \[\delta_t(T)\geq 25 \cdot 2^{k-2},\] with equality if and only if the tree formed by the internal vertices of \(T\) is the broom \(B(k,k-2)\) (see Figure 1).
Proof. First, let \(w\) be the unique leafless vertex in \(T\) and \(v_1,v_2,v_3\) be the neighbours of \(w\). Let \(T'\) be the tree formed by the internal vertices of \(T\). Consider the following cases:
Case 1. None of the vertices \(v_1,v_2,v_3\) is a leaf in \(T'\).
The set of all internal vertices in \(T\) except for \(w\), plus an arbitrary subset of the remaining vertices, is a TDS of \(T\). This already results in \(2^{k+3}\) TDS.
Case 2. One of the vertices \(v_1,v_2,v_3\) is a leaf in \(T'\).
Suppose \(v_1\) is a leaf in \(T'\). Let \(x_1,x_2\) be the leaves attached to \(v_1\) in \(T\). The set of all internal vertices in \(T\) except for \(w\), plus an arbitrary subset of the remaining vertices containing at least one of \(w,x_1\) and \(x_2\), is a TDS of \(T\). Thus, we already have at least \(7 \cdot 2^k\) TDS.
Case 3. Two of the vertices \(v_1,v_2,v_3\) are leaves in \(T'\).
In this case, \(B(k,k-2)\) is the tree formed by the internal vertices of \(T\). Suppose that \(v_1,v_2\) are leaves in \(T'\). Let \(x_1,x_2\) and \(x_3,x_4\) be the leaves attached to \(v_1\) and \(v_2\) respectively in \(T\). Every TDS of \(T\) must contain all internal vertices except for \(w\) (since they are support vertices). Once these are included, all vertices except for \(v_1\) and \(v_2\) are already totally dominated, so one can add an arbitrary subset of the remaining vertices provided that it either contains \(w\) or one of \(x_1,x_2\) and one of \(x_3,x_4\). Thus we have a total of \(2^{k+2}+9\cdot 2^{k-2}=25 \cdot 2^{k-2}\) TDS in \(T\).
Now, it only remains to observe that \(25 \cdot 2^{k-2} < 7 \cdot 2^k < 2^{k+3}\) to complete the proof. ◻
We now show that the tree with the minimum number of TDS among the trees with one leafless vertex has the second smallest number of TDS among all binary trees.
Theorem 2.4. ] For every \(k \geq 4\), the binary tree whose internal vertices form the broom \(B(k,k-2)\) is the binary tree of order \(2k+2\) with the second smallest number of TDS.
Proof. If the number \(k\) of internal vertices is \(4\), there are only two nonisomorphic binary trees, so the statement becomes trivial. Now assume that \(k \geq 5\), and let \(T\) be a binary tree with at least two leafless vertices, say \(w\) and \(w'\). By a similar approach as in Lemma 2.3, \(T\) has at least \(25 \cdot 2^{k-2}\) TDS that either contain all the internal vertices in \(T\), or all the internal vertices but \(w\). Moreover, the set of all vertices in \(T-\{w,w'\}\) is a TDS, thus \(\delta_t(T) \geq 25 \cdot 2^{k-2}+1\). By Lemma 2.3, this means that the tree whose internal vertices form the broom \(B(k,k-2)\) has fewer TDS. Combined with Corollary 2.2 and Lemma 2.3, this already yields the statement. ◻
In this section, we consider the upper bound for the number of TDS, which is more difficult to obtain. As a first step, we show that a binary tree with maximum number of TDS cannot have two distinct internal vertices that are each adjacent to precisely one leaf (see Proposition 3.3). The structure will be made more precise in Lemma 3.6, and fully characterized in Theorem 3.7 and Theorem 3.8. The extremal trees are unique up to isomorphism when the number of vertices \(n\) is not divisible by \(4\) (thus \(n \equiv 2 \mod 4\)), while they are not unique if \(n\) is divisible by \(4\).
In the following, we need several auxiliary quantities associated with rooted (binary) trees. Let \(T\) be a rooted tree, and \(v\) its root. We consider four different types of vertex subsets that are total dominating except possibly for \(v\). The vertex \(v\) can be included in such a set or not, and it can be totally dominated by the other vertices or not. This gives us a total of four combinations that are indicated by subscripts in the notation we use: the first subscript is \(1\) if \(v\) is included, and \(0\) otherwise; the second subscript is \(1\) if \(v\) is totally dominated (i.e., one of the neighbours of \(v\) is included in the set), and \(0\) otherwise. Thus the four possible combinations are as follows:
\(\bullet\) \(\delta_{11}(T,v)\) is the number of total dominating sets of \(T\) that include \(v\);
\(\bullet\) \(\delta_{01}(T,v)\) is the number of total dominating sets of \(T\) that do not include \(v\);
\(\bullet\) \(\delta_{10}(T,v)\) is the number of vertex subsets of \(T\) where \(v\) is included and all vertices but \(v\) are totally dominated;
\(\bullet\) \(\delta_{00}(T,v)\) is the number of vertex subsets of \(T\) where \(v\) is not included and all vertices but \(v\) are totally dominated;
Note that \(\delta_t(T) = \delta_{11}(T,v) + \delta_{01}(T,v)\). We start with the following lemma that relates the different quantities.
Lemma 3.1. Let \(T\) be a rooted binary tree with root \(v\). We have \[\begin{aligned} \delta_{11}(T,v) &\geq \delta_{01}(T,v), \text{ and} \\ \delta_{11}(T,v) &\geq 3\delta_{10}(T,v) \geq 3\delta_{00}(T,v). \end{aligned}\]
Proof. For every set \(D\) that is counted by \(\delta_{01}(T,v)\) (\(\delta_{00}(T,v)\), respectively), \(D \cup \{v\}\) is a set counted by \(\delta_{11}(T,v)\) (\(\delta_{10}(T,v)\), respectively). This is an injective relation, thus the two inequalities \(\delta_{11}(T,v) \geq \delta_{01}(T,v)\) and \(\delta_{10}(T,v) \geq \delta_{00}(T,v)\) follow immediately.
Next, let \(D\) be a set that is counted by \(\delta_{10}(T,v)\). By definition, \(D\) does not contain a neighbour of \(v\). If any nonempty subset of neighbours of \(v\) (there are three such subsets, since \(v\) has degree \(2\)) is added to \(D\), we obtain a set that is counted by \(\delta_{11}(T,v)\). Thus \(\delta_{11}(T,v) \geq 3\delta_{10}(T,v)\), completing the proof. ◻
In the following, we will use abbreviations to simplify our notation: for a tree \(T\) with root \(v\), we write \(T_{ab}\) instead of \(\delta_{ab}(T,v)\) for simplicity. Moreover, we need a version of this notation for birooted trees: in the following lemma, \(S\) is a tree with two distinguished vertices (roots) \(u\) and \(v\). We write \(S^{ab}_{cd}\) for the number of vertex subsets of \(S\) where all vertices, except possibly \(u\) and \(v\), are totally dominated. The indices \(a,b,c,d\) indicate the status of these two vertices: \(a = 1\) (\(c=1\), respectively) means that we count sets where \(u\) (\(v\)) is included. Otherwise, \(a = 0\) (\(c = 0\)). Likewise, \(b=1\) (\(d=1\), respectively) means that we count sets where \(u\) (\(v\)) is totally dominated. Otherwise, \(b=0\) (\(d=0\)). So for instance \(S_{10}^{01}\) is the number of vertex subsets of the tree \(S\) where all vertices except for \(u\) are totally dominated, and \(u\) is contained, but \(v\) is not.
Our next lemma describes the effect of a certain transformation on the number of total dominating sets.
Lemma 3.2. Suppose that a tree \(T\) can be decomposed as shown in Figure 2, where \(L\) and \(R\) are rooted binary trees with roots \(l\) and \(r\) respectively, \(S\) has distinguished vertices \(u\) and \(v\), and \(x_1\) and \(y_1\) are leaves adjacent to support vertices \(x\) and \(y\) respectively. Furthermore, consider the tree \(T'\) obtained by removing the edges \(xx_1\) and \(yr\) from \(T\) and replacing them by \(xr\) and \(yx_1\), thus exchanging \(R\) and the leaf \(x_1\) (see again Figure 2).
If both \(L\) and \(R\) are nontrivial rooted binary trees, i.e., if they have each more than one vertex, then \(\delta_t(T')>\delta_t(T)\).
Proof. With the notation introduced earlier, let us set \[\mathcal{L}_1 =\sum_{0 \leq b \leq 1} L_{1b}, \quad \mathcal{L}_0 =\sum_{0 \leq b \leq 1} L_{0b}, \quad \mathcal{R}_1 =\sum_{0 \leq b \leq 1} R_{1b}, \quad \text{ and } \quad \mathcal{R}_0 =\sum_{0 \leq b \leq 1} R_{0b}.\]
Also, let \(\mathcal{L}=\mathcal{L}_1+\mathcal{L}_0\) and \(\mathcal{R}=\mathcal{R}_1+\mathcal{R}_0\).
We start by determining the number \(\delta_t(T)\) of TDS of \(T\), first in the case that \(u \neq v\). For the leaves \(x_1\) and \(y_1\) to be totally dominated, every TDS of \(T\) must contain \(x\) and \(y\). Thus \(l,r,u,v\) are automatically totally dominated. Note also that the restriction of any TDS of \(T\) to \(L,R,S\) has to be total dominating except possibly for the vertices \(l,r,u,v\). We now distinguish different types of TDS depending on whether \(u\) and \(v\) are contained.
Let us start with TDS that contain both \(u\) and \(v\). There are \(\sum_{0\leq b,d\leq 1}S^{1b}_{1d}\) possibilities for the restriction to \(S\). Since \(u,v\) are assumed to be contained, \(x,y\) are already totally dominated. Thus there are \(\mathcal{L}\) possible choices for the restriction to \(L\) (\(l\) can be contained or not, and it can be totally dominated within \(L\) or not). Likewise, there are \(\mathcal{R}\) possible choices for the restriction to \(R\). Since we can also choose whether \(x_1,y_1\) are contained or not, we end up with \[4\mathcal{LR}\sum_{0\leq b,d\leq 1}S^{1b}_{1d},\] possible combinations in this case. Using a similar argument, we find that there are \[2\mathcal{R}(\mathcal{L}+\mathcal{L}_1)\sum_{0\leq b,d\leq 1}S^{0b}_{1d},\] possible TDS that contain \(v\), but not \(u\) (thus \(x\) needs to be totally dominated by either \(x_1\) or \(l\)). Analogously, there are \[2\mathcal{L}(\mathcal{R}+\mathcal{R}_1)\sum_{0\leq b,d\leq 1}S^{1b}_{0d}.\]
TDS containing \(u\), but not \(v\). Lastly, we get \[(\mathcal{LR}+\mathcal{L}\mathcal{R}_1 +\mathcal{R}\mathcal{L}_1 +\mathcal{L}_1\mathcal{R}_1 )\sum_{0\leq b,d\leq 1}S^{0b}_{0d},\] possible TDS containing neither \(u\) nor \(v\).
The combination of the four cases gives us the formula \[\begin{aligned} \delta_t(T) &=4\mathcal{LR}\sum_{0\leq b,d\leq 1}S^{1b}_{1d}+2\mathcal{R}(\mathcal{L}+\mathcal{L}_1)\sum_{0\leq b,d\leq 1}S^{0b}_{1d} +2\mathcal{L}(\mathcal{R}+\mathcal{R}_1)\sum_{0\leq b,d\leq 1}S^{1b}_{0d} \nonumber \\ &\quad+(\mathcal{LR}+\mathcal{L}\mathcal{R}_1 +\mathcal{R}\mathcal{L}_1 +\mathcal{L}_1\mathcal{R}_1 ) \sum_{0\leq b,d\leq 1}S^{0b}_{0d}\label{eLR1}. \end{aligned}\tag{1}\]
Now if \(u = v\), following similar reasoning, we have \[\delta_t(T) = 4\mathcal{LR}\sum_{0\leq b\leq 1}S_{1b} +(\mathcal{LR}+\mathcal{L}\mathcal{R}_1 +\mathcal{R}\mathcal{L}_1 +\mathcal{L}_1\mathcal{R}_1 )\sum_{0\leq b\leq 1}S_{0b}\label{eLR2}.\tag{2}\]
Next suppose that there are no vertices in \(S\), and that instead \(xy\) is an edge of \(T\). Again by similar reasoning, we have \[\delta_t(T) = 4\mathcal{LR}.\label{eLR3}\tag{3}\]
Next we determine the number \(\delta_t(T')\) of TDS of \(T'\), first in the case that \(u\neq v\). For the leaves \(x_1\) and \(y_1\) to be totally dominated, every TDS of \(T'\) must contain \(y\), so \(v\) is automatically totally dominated as well. Again, we distinguish different types of TDS depending on whether or not \(u,v\) are contained.
If \(v\) is not contained in a TDS, then either \(x_1\) or \(y_1\) needs to be for \(y\) to be totally dominated, giving us three possibilities for \(x_1,y_1\). If \(v\) is contained in a TDS, then we have four possibilities instead.
For \(u\), we have four possible situations in a TDS: if \(u\) is contained and also totally dominated inside of \(S\), then there are \(\mathcal{LR}+\delta_t(L)\delta_t(R)\) possibilities for the restriction to \(\{x\} \cup L \cup R\) (\(\mathcal{LR}\) where \(x\) is contained in the set, \(\delta_t(L)\delta_t(R)\) where it is not). If \(u\) is contained in a TDS, but not totally dominated inside of \(S\), then \(x\) must be an element, and there are \(\mathcal{LR}\) possibilities. If \(u\) is not contained in the set, but totally dominated by a neighbour in \(S\), then there are \(\mathcal{LR}-\mathcal{L}_0\mathcal{R}_0\) possibilities including \(x\) and \(L_{11}R_{11}+L_{01}R_{11}+L_{11}R_{01}\) not including it. Lastly, if \(u\) is neither included in a TDS nor totally dominated by a neighbour in \(S\), then we have \(\mathcal{LR}-\mathcal{L}_0\mathcal{R}_0\) possibilities. Combining all these gives us the formula \[\begin{aligned} \delta_t(T') &= \big(\mathcal{LR}+\delta_t(L)\delta_t(R)\big) \sum_{0\leq d\leq 1}(4S^{11}_{1d} +3S^{11}_{0d}) \nonumber \\ &\quad+ \big(\mathcal{LR}-\mathcal{L}_0\mathcal{R}_0 +L_{11}R_{11} +L_{01}R_{11}+L_{11}R_{01}\big) \sum_{0\leq d\leq 1}(4S^{01}_{1d} +3S^{01}_{0d}) \nonumber \\ &\quad +\mathcal{LR}\sum_{0\leq d\leq 1}(4S^{10}_{1d} +3S^{10}_{0d})+ \big(\mathcal{LR}-\mathcal{L}_0\mathcal{R}_0\big)\sum_{0\leq d\leq 1}(4S^{00}_{1d} +3S^{00}_{0d}). \label{eLR4} \end{aligned}\tag{4}\]
Now if \(u=v\), by similar reasoning we have \[\begin{aligned} \delta_t(T') &= 4\big(\mathcal{LR}+\delta_t(L)\delta_t(R)\big)(S_{11} +S_{10}) \nonumber \\ &\quad+ 3\big(\mathcal{LR}-\mathcal{L}_0\mathcal{R}_0+L_{11}R_{11}+L_{01}R_{11}+L_{11}R_{01}\big)(S_{01}+S_{00}). \label{eLR5} \end{aligned}\tag{5}\]
Finally, if there are no vertices in \(S\), and instead an edge between \(x\) and \(y\), we have \[\delta_t(T') = 4\mathcal{LR} +3\delta_t(L)\delta_t(R).\label{eLR6}\tag{6}\]
It remains to show that if \(|L|,|R|>1\), then \(\delta_t(T')>\delta_t(T)\) in all three cases. Set \(\Delta_t = \delta_t(T')-\delta_t(T)\). If \(u \neq v\), then by (1) and (4) we have \[\begin{aligned} \Delta_t &= \alpha_1\sum_{0\leq d\leq 1}S^{11}_{1d}+\alpha_2\sum_{0\leq d\leq 1}S^{11}_{0d} +\alpha_3\sum_{0\leq d\leq 1}S^{01}_{1d}+\alpha_4\sum_{0\leq d\leq 1}S^{01}_{0d} \nonumber \\ &\quad+\alpha_5\sum_{0\leq d\leq 1}S^{00}_{1d} +\alpha_6\sum_{0\leq d\leq 1}S^{10}_{0d}+\alpha_7\sum_{0\leq d\leq 1}S^{00}_{0d}, \end{aligned}\] where \[\begin{aligned} \alpha_1 &= 4\delta_t(L)\delta_t(R),\\ \alpha_2 &= \mathcal{L}\mathcal{R}+3\delta_t(L)\delta_t(R)-2\mathcal{L}\mathcal{R}_1,\\ \alpha_3 &= 2\mathcal{L}_0\mathcal{R}-4\mathcal{L}_0\mathcal{R}_0+4L_{11}R_{11}+4L_{01}R_{11}+4L_{11}R_{01},\\ \alpha_4 &= 2\mathcal{L}\mathcal{R}-\mathcal{L}\mathcal{R}_1 -\mathcal{R}\mathcal{L}_1 -\mathcal{L}_1\mathcal{R}_1-3\mathcal{L}_0\mathcal{R}_0+3L_{11}R_{11}+3L_{01}R_{11}+3L_{11}R_{01},\\ \alpha_5 &= 2\mathcal{L}\mathcal{R}-2\mathcal{L}_1\mathcal{R}-4\mathcal{L}_0\mathcal{R}_0,\\ \alpha_6 &= \mathcal{L}\mathcal{R}-2\mathcal{L}\mathcal{R}_1= \mathcal{L}(\mathcal{R}_0-\mathcal{R}_1), \text{ and} \\ \alpha_7 &= 2\mathcal{L}\mathcal{R}-\mathcal{L}\mathcal{R}_1-\mathcal{L}_1\mathcal{R}-\mathcal{L}_1\mathcal{R}_1 -3\mathcal{L}_0\mathcal{R}_0 = \mathcal{R}_0(\mathcal{L}_1-\mathcal{L}_0)+\mathcal{R}_1(\mathcal{L}_0-\mathcal{L}_1). \end{aligned}\]
We show that the first five of these coefficients (\(\alpha_1\) to \(\alpha_5\)) are all non negative. First, \(\alpha_1\) is trivially strictly positive. Next, \[\begin{aligned} \alpha_2 &= \mathcal{L}\mathcal{R}+3\delta_t(L)\delta_t(R)-2\mathcal{L}\mathcal{R}_1 =\mathcal{L}\mathcal{R}_0+3\delta_t(L)\delta_t(R)-\mathcal{L}\mathcal{R}_1\\ &= \mathcal{L}\mathcal{R}_0 + 2L_{11}R_{11}+3L_{11}R_{01}+2L_{01}R_{11}+3L_{01}R_{01} \\ &\quad -L_{11}R_{10}-L_{01}R_{10}-L_{10}R_{11}-L_{10}R_{10}-L_{00}R_{11}-L_{00}R_{10}\\ &\geq 2L_{11}R_{11}-L_{11}R_{10}-L_{01}R_{10}-L_{10}R_{11}-L_{10}R_{10}-L_{00}R_{11}-L_{00}R_{10}. \end{aligned}\]
By Lemma 3.1, we have \(L_{11} \geq 3L_{10}\) and \(R_{11} \geq 3R_{10}\), so \(2L_{11}R_{11} = L_{11}R_{11} + L_{11}R_{11} \geq 3L_{10}R_{11}+ 3L_{11}R_{10}\) and thus \[\begin{aligned} \alpha_2 &\geq 3L_{11}R_{10}+3L_{10}R_{11}-L_{11}R_{10}-L_{01}R_{10}-L_{10}R_{11} -L_{10}R_{10}-L_{00}R_{11}-L_{00}R_{10} \\ &= 2L_{11}R_{10}+2L_{10}R_{11}-L_{01}R_{10}-L_{10}R_{10}-L_{00}R_{11}-L_{00}R_{10}. \end{aligned}\]
Since also \(L_{11} \geq L_{01}\), \(L_{11} \geq L_{00}\), \(L_{10} \geq L_{00}\), and \(R_{11} \geq R_{10}\) by Lemma 3.1, it follows that \(\alpha_2 \geq 0\).
Next, observe that \(\mathcal{L}_1,\mathcal{R}_1 > 0\) and \(\mathcal{L}_0,\mathcal{R}_0 \geq 0\). Also, \(\mathcal{L}_1-\mathcal{L}_0\geq 0\) and \(\mathcal{R}_1-\mathcal{R}_0\geq 0\) by Lemma 3.1. Thus, we immediately get \[\alpha_3 = 2\mathcal{L}_0(\mathcal{R}_1-\mathcal{R}_0)+4 L_{11}R_{11}+4L_{01}R_{11}+4L_{11}R_{01} \geq 0\] and \[\alpha_5 = 2\mathcal{L}\mathcal{R}-2\mathcal{L}_1\mathcal{R}-4\mathcal{L}_0\mathcal{R}_0 = 2 \mathcal{L}_0\mathcal{R} – 4\mathcal{L}_0\mathcal{R}_0 = 2\mathcal{L}_0(\mathcal{R}_1-\mathcal{R}_0) \geq 0.\]
Similarly, since \(\mathcal{L}_1-\mathcal{L}_0 \geq 0\), we have \[\begin{aligned} \alpha_4 &=\mathcal{R}_0(\mathcal{L}_1-\mathcal{L}_0)+\mathcal{R}_1(\mathcal{L}_0-\mathcal{L}_1)+3L_{11}R_{11}+3L_{01}R_{11} +3L_{11}R_{01} \\ &\geq 3L_{11}R_{11}-\mathcal{L}_1\mathcal{R}_1=2L_{11}R_{11}-L_{11}R_{10}-L_{10}R_{11}-L_{10}R_{10}\nonumber \\ &\geq 3L_{11}R_{10}+3L_{10}R_{11}-L_{11}R_{10}-L_{10}R_{11}-L_{10}R_{10} \geq 0. \end{aligned}\]
Since we have now established that \(\alpha_2, \alpha_4, \alpha_5 \geq 0\), it follows that \[\begin{aligned} \Delta_t &\geq \alpha_1\sum_{0\leq d\leq 1}S^{11}_{1d} +\alpha_3\sum_{0\leq d\leq 1}S^{01}_{1d} +\alpha_6\sum_{0\leq d\leq 1}S^{10}_{0d}+\alpha_7\sum_{0\leq d\leq 1}S^{00}_{0d}.\label{eLR7} \end{aligned}\tag{7}\]
Recall that we are assuming \(u \neq v\). For every set that is counted by \(S^{10}_{01}\) or \(S^{10}_{00}\), we can add \(v\) to it plus a neighbour of \(u\) to obtain a set that is counted by \(S^{11}_{11}\) and \(S^{11}_{10}\) respectively. Hence, we have \[\label{eLR8a} S^{11}_{11}\geq S^{10}_{01}, \quad S^{11}_{10} \geq S^{10}_{00},\tag{8}\] and analogously \[\label{eLR8b} S^{01}_{11} \geq S^{00}_{01}, \quad S^{01}_{10} \geq S^{00}_{00}.\tag{9}\]
Thus \(\sum_{0\leq d\leq 1}S^{11}_{1d} \geq \sum_{0\leq d\leq 1}S^{10}_{0d}\) and \(\sum_{0\leq d\leq 1}S^{01}_{1d} \geq \sum_{0\leq d\leq 1}S^{00}_{0d}\) in (7), which gives us \[\begin{aligned} \Delta_t &\geq \delta_t(L)\delta_t(R) \sum_{0\leq d\leq 1}S^{11}_{1d} +(3\delta_t(L)\delta_t(R)+\alpha_6)\sum_{0\leq d\leq 1}S^{10}_{0d} +(\alpha_3+\alpha_7)\sum_{0\leq d\leq 1}S^{00}_{0d}. \end{aligned}\]
Finally, we make use of Lemma 3.1 again to obtain \[\begin{aligned} 3\delta_t(L)\delta_t(R)+\alpha_6 &\geq 3\delta_t(L) R_{11} – \mathcal{L}\mathcal{R}_1 \\ &= 3(L_{01} + L_{11})R_{11} – (L_{00} + L_{01} + L_{10} + L_{11})(R_{10}+R_{11}) \\ &\geq 3(L_{01} + L_{11})R_{11} – \left(L_{01} + \tfrac53 L_{11}\right) \cdot \tfrac43 R_{11} \\ &= \left(\tfrac53 L_{01} + \tfrac79 L_{11}\right) R_{11} > 0 \end{aligned}\] and \[\begin{aligned} \alpha_3+\alpha_7 &= 2\mathcal{L}_0\mathcal{R}-4\mathcal{L}_0\mathcal{R}_0+4L_{11}R_{11}+4L_{01}R_{11}+4L_{11}R_{01} + \mathcal{R}_0(\mathcal{L}_1-\mathcal{L}_0)+\mathcal{R}_1(\mathcal{L}_0-\mathcal{L}_1) \\ &= \mathcal{L}_0 (2\mathcal{R} – 4\mathcal{R}_0 + \mathcal{R}_1 – \mathcal{R}_0) + \mathcal{L}_1(\mathcal{R}_0 – \mathcal{R}_1) +4L_{11}R_{11}+4L_{01}R_{11}+4L_{11}R_{01} \\ &= 3\mathcal{L}_0(\mathcal{R}_1 – \mathcal{R}_0) + \mathcal{L}_1(\mathcal{R}_0 – \mathcal{R}_1) +4L_{11}R_{11}+4L_{01}R_{11}+4L_{11}R_{01} \\ &\geq 4L_{11}R_{11} – \mathcal{L}_1\mathcal{R}_1 \geq 4L_{11}R_{11} – \tfrac43 L_{11} \cdot \tfrac43 R_{11} > 0. \end{aligned}\]
So we can conclude that \[\begin{aligned} \Delta_t& \geq \delta_t(L)\delta_t(R) \sum_{0\leq d\leq 1}S^{11}_{1d} > 0, \end{aligned}\] in the case that \(u \neq v\). If \(u=v\), then we have \[\Delta_t = \alpha_1(S_{11}+S_{10}) + \alpha_4(S_{01} + S_{00}).\]
Since \(\alpha_4 \geq 0\), \[\Delta_t \geq \alpha_1(S_{11}+S_{10}) = 4\delta_t(L)\delta_t(R)(S_{11} + S_{10}) >0.\]
Lastly, if there is an edge between \(x\) and \(y\) and \(S\) is empty, then we simply have \(\Delta_t=3\delta_t(L)\delta_t(R)>0\). ◻
From Lemma 3.2, we immediately get the following partial characterization of binary trees with maximum number of TDS.
Proposition 3.3. In a binary tree \(T\) with maximum number of TDS among all binary trees of the same order, there cannot be two internal vertices adjacent to exactly one leaf each. In other words, with at most one exception all internal vertices are leafless or adjacent to two leaves.
Proof. If there were two such vertices \(x\) and \(y\), then we could decompose the tree as in Lemma 3.2 and obtain a new tree \(T'\) of the same order with more TDS, which is an immediate contradiction. ◻
In the proof of the next lemma and proofs of our main theorems, we will use the following lemma from [11].
Lemma 3.4. (see [11, Lemma 2]) Let \(T_1\) and \(T_2\) be two trees, and let \(u,v\) be vertices of \(T_1\) and \(T_2\), respectively. Consider the tree \(T\) obtained by adding the edge \(uv\) to the union \(T_1 \cup T_2\). We have \[\begin{aligned} \delta_t(T) \geq\delta_t(T_1)\delta_t(T_2), \end{aligned}\] with equality if and only if \(u\) and \(v\) are precisely a distance of \(2\) away from a leaf in \(T_1\) and \(T_2\), respectively (\(u\) and \(v\) may themselves be leaves).
If a binary tree has more than four vertices, and there is no internal vertex adjacent to exactly one leaf, then the internal vertices induce a binary tree. Thus the number of internal vertices must be even, which in turn implies that the total number of vertices is of the form \(4k+2\) (\(2k\) internal vertices, \(2k+2\) leaves). On the other hand, if there is one internal vertex adjacent to exactly one leaf, then the number of internal vertices must be odd, and the total number of vertices is a multiple of \(4\).
When an edge \(e\) of a binary tree \(T\) is removed, each of the two components can be considered as a rooted binary tree (rooted at one of the ends of \(e\)). We call any such rooted binary tree a branch of \(T\). In the following, by a binary branch of type \(X\) (or \(X\)–branch for short), we mean a branch whose shape is as shown in Figure 3. The number of leafless internal vertices (\(x\) in the figure) will be called the length of such a branch. An \(X\)-branch of length \(x\) has \(4x+3\) vertices. Note that \(x = 0\) is allowed as well.
For later purposes, we will need the number of TDS in an \(X\)-branch. If the length \(x\) is \(0\), then this number is easily seen to be \(3\), so suppose that \(x > 0\). When \(x = 1\), there are 25 TDS: both support vertices have to be included. If the root \(v_1\) is also included, one can add an arbitrary subset of leaves, for which there are \(2^4\) possibilities. Otherwise, one needs to include at least one neighbour of each support vertex, giving us \(3^2\) possibilities for a total of \(2^4 + 3^2 = 25\).
For \(x > 1\), we can apply Lemma 3.4. Since the vertices \(v_1,v_2,\ldots,v_x\) in Figure 3 are all at distance \(2\) from a leaf, we can express the number of TDS as a product of \(x-1\) factors \(7\) (the number of TDS in a \(4\)-vertex star) and one factor \(25\). Thus the number of TDS of an \(X\)-branch of length \(x\) is \(25 \cdot 7^{x-1}\). Of those, \(16\) contain the root \(v_x\) if \(x = 1\), and \(4 \cdot 25 \cdot 7^{x-2} = 100 \cdot 7^{x-2}\) if \(x = 1\).
Alternatively, one can also obtain these formulas by a direct argument, noticing that all support vertices have to be included in a TDS, and additionally at least one neighbour of each support vertex.
Lemma 3.5. Let \(T\) consist of the vertex \(w\) and branches \(A,B,S\) that are rooted at the neighbours \(v_a,v_b,v\) of \(w\), respectively. Suppose that \(A\) and \(B\) are \(X\)-branches of length \(a\) and \(b\), respectively (\(a \geq b \geq 1\)), see Figure 4. Then we have \[\label{eAA1} \delta_t(T)= 7^{a+b-4} \left( 30625(2S_{11}+S_{10})+ \begin{cases} 26656(2S_{01}+S_{00}),& a = b= 1, \\ 25900(2S_{01}+S_{00}), & a > 1, b = 1, \\ 25000(2S_{01}+S_{00}), & a,b > 1. \end{cases} \right)\tag{10}\]
Now let \(T'\) consist of the same branch \(S\) (rooted at \(v\)) as in \(T\) and an \(X\)-branch \(C\) of length \(a+b+1\) (rooted at \(v_c\), which is connected to \(v\) by an edge), see Figure 5. Then we have \[\label{eAA2} \delta_t(T')= 7^{a+b-4} \big(60025(S_{11}+S_{01})+34300(S_{10}+S_{00})\big).\tag{11}\]
Observe that \(T\) and \(T'\) are of the same order. If \(v\) is either a leaf or a leafless internal vertex, then \(\delta_t(T') > \delta_t(T)\).
Proof. We begin with the tree \(T\). For any TDS \(D\) of \(T\), consider \(D'= D \cap V(S)\). Note that \(D'\) must totally dominate all vertices of \(S\) except possibly \(v\). We consider four different cases, depending on whether \(v\) is contained in \(D'\) or not, and whether it is totally dominated or not. The number of possibilities for the set \(D'\) is then \(S_{11},S_{10},S_{01}\), or \(S_{00}\), respectively. In each case, we determine the number of possibilities for the set \(D \setminus D'\), which is a vertex subset of \(A \cup B \cup \{w\}\).
\(\bullet\) Suppose first that \(D'\) is total dominating in \(S\), and that it contains \(v\), so that \(w\) is totally dominated by \(v\). There are \(S_{11}\) possibilities for \(D'\) in this case. Note that all support vertices of \(A\) and \(B\) are necessarily contained in \(D\), so that all leafless internal vertices (in particular \(v_a,v_b\)) are automatically totally dominated. Hence one can freely choose whether or not to include \(w\). So \(D \setminus D'\) consists of arbitrary TDS in \(A\) and \(B\), and possibly \(w\). Since \(A\) is an \(X\)-branch of length \(a\), it has \(25 \cdot 7^{a-1}\) TDS as observed earlier. Likewise, \(B\) has \(25 \cdot 7^{b-1}\) TDS. Thus there are \(2 \cdot 25 \cdot 7^{a-1} \cdot 25 \cdot 7^{b-1} \cdot S_{11} = 1250 \cdot 7^{a+b-2}S_{11}\) possible combinations in total.
\(\bullet\) Next consider the case that \(D'\) contains \(v\), but that \(v\) is not totally dominated. There are \(S_{10}\) possibilities for \(D'\) with this property. We need to include \(w\), but can otherwise choose arbitrary TDS in \(A\) and \(B\) as in the previous case, giving us \(625 \cdot 7^{a+b-2}S_{10}\) combinations.
\(\bullet\) If \(D'\) is total dominating in \(S\), but does not contain \(v\), then at least one of \(v_a\) and \(v_b\) must be contained in \(D\). Apart from that, \(D \setminus D'\) consists of arbitrary TDS in \(A\) and \(B\), and possibly \(w\). We have to split into three subcases depending on the values of \(a\) and \(b\):
\(\bullet\) \(a = b = 1\). In this case, \(A\) and \(B\) both have \(25\) TDS, \(16\) of which contain the root while the other \(9\) do not. Thus we find that \(T-S\) has \[2 \cdot (16^2 + 2 \cdot 16 \cdot 9) = 1088.\]
TDS that contain at least one of \(v_a,v_b\) (the initial factor \(2\) takes vertex \(w\) into account).
\(\bullet\) \(b = 1\), but \(a > 1\). Here, \(A\) has \(100 \cdot 7^{a-2}\) TDS that contain \(v_a\) and \(75 \cdot 7^{a-2}\) TDS that do not contain it. Thus \(T-S\) has \[2 \cdot (16 \cdot 100 \cdot 7^{a-2} + 16 \cdot 75 \cdot 7^{a-2} + 9 \cdot 100 \cdot 7^{a-2}) = 7400 \cdot 7^{a-2}.\]
TDS that contain at least one of \(v_a,v_b\).
\(\bullet\) \(a,b > 1\). Now, an analogous calculation yields that \(T-S\) has \[2 \cdot (100^2 \cdot 7^{a-2+b-2} + 2 \cdot 100 \cdot 75 \cdot 7^{a-2+b-2}) = 50000 \cdot 7^{a+b-4}.\]
TDS that contain at least one of \(v_a,v_b\).
In each case, we multiply by the number of possibilities for \(D'\), which is \(S_{01}\).
\(\bullet\) Lastly, if \(D'\) does not contain \(v\) and does not totally dominate it either, then \(w\) and at least one of \(v_a\) and \(v_b\) must be included in \(D\). Distinguishing the same three cases as before, we have \(544\) possibilities for \(D \setminus D'\) if \(a=b=1\), \(3700 \cdot 7^{a-2}\) possibilities if \(b=1\), but \(a > 1\), and \(25000 \cdot 7^{a+b-4}\) possibilities if \(a,b > 1\). In each case, we multiply by the number of possibilities for \(D'\), which is \(S_{00}\).
Combining all four cases and factorising, we get (10).
In the same way, for any TDS \(D\) of \(T'\), consider \(D' = D \cap V(S)\), and distinguish the same four cases as before. If \(v\) is totally dominated in \(D'\), then \(D \setminus D'\) can be an arbitrary TDS of \(C\), for which there are \(25 \cdot 7^{c-1}\) possibilities. This gives us \(25 \cdot 7^{c-1}(S_{11}+S_{01})\) possible combinations. If \(D'\) does not totally dominate \(v\), then \(v_c\) needs to be included in \(D \setminus D'\), giving us \(100 \cdot 7^{c-2}\) possibilities for \(D \setminus D'\) and thus \(100 \cdot 7^{c-2}(S_{10}+S_{00})\) possible combinations. Again, combining the cases and factorising gives us (11).
It remains to verify that \(\delta_t(T') > \delta_t(T)\) if \(v\) is either a leaf or a leafless internal vertex. With \(c = a+b+1\), (10) and (11) give us \[\delta_t(T')-\delta_t(T)= 7^{a+b-4}\left( 1225(-S_{11}+3S_{10}) + \begin{cases} 6713S_{01}+7644S_{00},& a = b= 1, \\ 8225S_{01}+8400S_{00}, & a > 1, b = 1, \\ 10025S_{01}+9300S_{00}, & a,b > 1. \end{cases} \right)\]
So for certain real numbers \(\alpha,\beta\) with \(5 < \alpha,\beta <9\), we have \[\begin{aligned} \delta_t(T')-\delta_t(T)&= 1225 \cdot 7^{a+b-4} (-S_{11}+\alpha S_{01}+3S_{10}+\beta S_{00}). \label{eAA4} \end{aligned}\tag{12}\]
It remains to show that \(-S_{11}+\alpha S_{01}+3S_{10}+\beta S_{00}\) is positive by considering the following cases.
Case 1: \(v\) is a leaf. Plugging \(S_{11}=0\), \(S_{01}=0\), \(S_{10}=1\), and \(S_{00}=1\) into (12) shows that \(\delta_t(T')>\delta_t(T)\).
Case 2: \(v\) is an internal vertex. Let \(x\) and \(y\) be the neighbours of \(v\) in \(S\). Since we are assuming that \(v\) is leafless, neither of the neighbours is a leaf. Thus \(S_{11}, S_{01}>0\).
Let \(D\) be a TDS of \(S\) that contains \(v\). If we remove \(v\) from \(D\), \(D-\{v\}\) still totally dominates \(v\) but might not totally dominate \(x\) and \(y\). If \(D-\{v\}\) totally dominates \(x\) and \(y\), then it is a set counted by \(S_{01}\). Otherwise, if \(x\) or \(y\) is not totally dominated by \(D-\{v\}\), we add exactly one of its neighbours to \(D-\{v\}\) to form a set \(D'\) that is counted by \(S_{01}\). Since we are (at most) adding one neighbour for each of \(x\) and \(y\), we can have at most four sets counted by \(S_{11}\) that map to the same set \(D'\). Thus \(S_{11} \leq 4S_{01}\) and therefore \[-S_{11}+\alpha S_{01}+3S_{10}+\beta S_{00} \geq (\alpha-4)S_{01}+3S_{10}+\beta S_{00}>0,\] completing the proof. ◻
Lemma 3.6. Let \(n\) be a multiple of \(4\), \(n \geq 8\), and suppose that the binary tree \(T\) has the maximum number of TDS among all binary trees with \(n\) vertices. Let \(u\) be the unique internal vertex that is adjacent to exactly one leaf (which exists by Proposition 3.3). Let this leaf neighbour be \(v\), let \(R\) and \(S\) be the two branches rooted at the other two neighbours of \(u\), and let \(R_1,R_2,S_1,S_2\) be the sub-branches of \(R\) and \(S\) as in Figure 6 (which must exist since the roots of \(R\) and \(S\) cannot be leaves). Then each of \(R_1,R_2,S_1,S_2\) is either of type \(X\) or a single vertex.
Proof. Assume to the contrary that one of \(R_1,R_2,S_1,S_2\) is neither a single vertex nor of type \(X\). For each internal vertex \(w\) in \(R_1 \cup R_2 \cup S_1 \cup S_2\), consider the branch of \(T\) that consists of \(w\) and all vertices for which the unique path to \(u\) passes through \(w\) (i.e., everything “below” \(w\) in Figure 6). Pick \(w\) in such a way that this branch, which we denote by \(B\), is not of type \(X\) and is minimal with this property. Such a branch must exist by our assumption on \(R_1,R_2,S_1,S_2\). Then each of the sub-branches \(B_1\) and \(B_2\) of \(B\) that are rooted at neighbours \(w_1\) and \(w_2\) of \(w\) must be a single vertex or of type \(X\) (by minimality of \(B\)). If both \(B_1\) and \(B_2\) are single vertices, then \(B\) is of type \(X\), a contradiction. If one of them is a single vertex, but the other is not, then \(w\) has exactly one leaf neighbour, which is also impossible (since \(u\) is the only such vertex).
Thus \(B_1\) and \(B_2\) are both of type \(X\). If either of them has length \(0\), then the entire branch \(B\) is of type \(X\) as well, which is a contradiction. Thus we are exactly in the situation of Lemma 3.5: we can replace \(B\) by a single branch of type \(X\), which yields a tree \(T'\) with \(\delta_t(T') > \delta_t(T)\) by Lemma 3.5. The lemma applies since the neighbour of \(w\) other than \(w_1,w_2\) must be leafless (it lies on the path between \(w\) and \(u\), and it cannot have a single leaf neighbour since the only such vertex is \(u\)). This contradicts the assumptions on \(T\), thus completing the proof. ◻
Theorem 3.7. Let \(n\) be a multiple of \(4\), and let \(T\) be a binary tree of order \(n\) that has the maximum number of TDS among all trees of order \(n\).
\(\bullet\) If \(n = 4\), then \(T\) is a star and \(\delta_t(T) = 7\).
\(\bullet\) If \(8 \leq n \leq 16\), then \(T\) is of the form shown in Figure 7, with \(\delta_t(T) = 32,200,1400\) for \(n=8,12,16\) respectively.
\(\bullet\) If \(n \geq 20\), then \(T\) is of the form shown in Figure 8, where \(a,b\) are positive integers with \(a+b = \frac{n}{4} – 3\), and
\(\bullet\) \(\delta_t(T) = 10000 \cdot 7^{\frac{n-20}{4}}\).
Proof. The case \(n=4\) is trivial, so assume that \(n \geq 8\). By Lemma 3.6, we already know that \(T\) must be of the form shown in Figure 6, where \(R_1,R_2,S_1,S_2\) are either single vertices or \(X\)-branches. If \(R_1\) is a single vertex, then so is \(R_2\), and vice versa, since \(u\) is the only vertex that has exactly one leaf neighbour. The same applies to \(S_1\) and \(S_2\). This leaves us with the following cases:
Case 1: \(|R_1|=|R_2|=|S_1|=|S_2| = 1\). In this case, \(n=8\) and \(T\) is of the form shown in Figure 7. It is easy to compute \(\delta_t(T) = 32\). Since this is in fact the only binary tree of order \(8\) up to isomorphism, the statement is trivial in this case.
Case 2: \(|R_1|=|R_2| = 1\) or \(|S_1|=|S_2| = 1\), but not both. Without loss of generality, we can assume the former. Now \(S_1,S_2\) must be \(X\)-branches, and it follows that \(T\) is of the form shown in Figure 8 for some nonnegative integers \(a,b\) with \(a+b = \frac{n}{4} – 3\). This implies that \(n \geq 12\). By means of (11), we find that \(\delta_t(T) = 200 \cdot 7^{\frac{n-12}{4}}\) if \(a = 0\) or \(b = 0\), and (10) yields \(\delta_t(T) = 10000 \cdot 7^{a+b-2} = 10000 \cdot 7^{\frac{n-20}{4}}\) if \(a,b > 0\) (which is only possible for \(n \geq 20\)). Since \(10000 \cdot 7^{\frac{n-20}{4}} > 200 \cdot 7^{\frac{n-12}{4}}\), the former can be excluded for \(n \geq 20\).
Case 3: \(R_1,R_2,S_1,S_2\) are \(X\)-branches. This means that \(T\) has the shape shown in Figure 9 for some nonnegative integers \(a,b,c,d\) (the lengths of \(R_1,R_2,S_1,S_2\), respectively). There are the following possibilities:
(a) \(a=c=0\) (or \(a=d=0\), \(b=c=0\), \(b=d=0\)). This means that \(R\) and \(S\) are both \(X\)-branches. By Lemma 3.5, \(T\) cannot have the maximum number of TDS in this case.
(b) \(a=b=0\), but \(c,d > 0\) (or \(c=d=0\) and \(a,b > 0\)). We can apply Lemma 3.4 to the two edges other than \(uw_1\) that are incident with \(w_1\), which gives us \[\delta_t(T) = 91 \cdot 25 \cdot 7^{c-1} \cdot 25 \cdot 7^{d-1} = 56875 \cdot 7^{c+d-2} = 56875 \cdot 7^{\frac{n-24}{4}},\] where necessarily \(n\geq 24\).
(c) exactly one of \(a,b,c,d\) (without loss of generality \(a\)) equals \(0\). Applying Lemma 3.4 in the same way as before to edges incident with \(w_1\) and \(w_2\), we get \[\delta_t(T)= 25 \cdot 25 \cdot 7^{b-1} \cdot 25 \cdot 7^{c-1} \cdot 25 \cdot 7^{d-1} = 390625 \cdot 7^{\frac{n-28}{4}},\] where \(n\geq 28\).
(d) \(a,b,c,d >0\). Again, Lemma 3.4 applies, and we obtain \(\delta_t(T)=390625 \cdot 7^{\frac{n-28}{4}}\) (with \(n \geq 32\)) as in the previous case.
Since both \(56875 \cdot 7^{\frac{n-24}{4}} < 10000 \cdot 7^{\frac{n-20}{4}}\) and \(390625 \cdot 7^{\frac{n-28}{4}} < 10000 \cdot 7^{\frac{n-20}{4}}\), Case 3 cannot yield the maximum number of TDS (the trees depicted in Figure 8 have a greater number of TDS). As we have covered all cases, the proof is complete. ◻
Theorem 3.8. Let \(n \equiv 2 \mod 4\), \(n \geq 6\), and suppose that the binary tree \(T\) has the maximum number of TDS among all binary trees with \(n\) vertices. Then \(T\) is of the form shown in Figure 10, and \[\delta_t(T) = \begin{cases} 16, & n = 6, \\ 91, & n = 10, \\ 625 \cdot 7^{\frac{n-14}{4}}, & n \geq 14. \end{cases}\]
Proof. Every binary tree \(T\) with at least three vertices can be decomposed as shown in Figure 11, where \(R\) is a branch. This is true since \(T\) will always have an internal vertex that is a leaf in the subtree induced by its internal vertices and therefore has two leaf neighbours. As in the proof of Lemma 3.6, \(R\) can be split further into its root and two subbranches \(R_1\) and \(R_2\). By the same argument as in the proof of Lemma 3.6, \(R_1\) and \(R_2\) have to be single vertices or \(X\)-branches. If both are single vertices, then \(n = 6\) and there is nothing to prove as there is only one binary tree with \(6\) vertices up to isomorphism. If exactly one of them is a single vertex, then the root of \(R\) has exactly one leaf neighbour. Since we are assuming \(n \equiv 2 \mod 4\), there would have to be a second vertex with this property (if there is only one, then \(n\) has to be a multiple of \(4\), as has been mentioned earlier). However, this has been ruled out by Proposition 3.3. So the only possibility that remains is that \(R_1\) and \(R_2\) are both \(X\)-branches. In this case, \(T\) is of the form shown in Figure 10. The formula for \(\delta_t(T)\) follows easily, either by a direct argument based on the observation that all support vertices have to be included in a TDS, plus at least one neighbour of each support vertex, or by splitting \(T\) into two \(X\)-branches and applying Lemma 3.4. ◻
To summarize, the maximum number of TDS in a binary tree with \(n\) vertices is given by Table 1 for \(n \leq 16\), and otherwise by \[\max_{|T| =n} \delta_t(T) = \begin{cases} 10000 \cdot 7^{\frac{n-20}{4}}, & n \equiv 0 \mod 4, \\ 625 \cdot 7^{\frac{n-14}{4}}, & n \equiv 2 \mod 4. \end{cases}\]
| \(n\) | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 |
|---|---|---|---|---|---|---|---|---|
| \(\max_{|T| =n} \delta_t(T)\) | 1 | 7 | 16 | 32 | 91 | 200 | 625 | 1400 |
The first author was supported by Deutscher Akademischer Austauschdienst (DAAD), German Academic Exchange Service, under the In-Region PhD Scholarship Programme/African Institute for Mathematical Sciences, with reference number 91735615.
The second author was supported by the National Research Foundation of South Africa (Grant Number: 121931).
The third author was supported by the Swedish research council (VR), grant 2022-04030.