Conditions for Spanning Trees Whose Internal Subtrees Have Few Branch Vertices and Leaves

Abstract

Let T be a tree. The sets of leaves and branch vertices of T are denoted by L(T) and B(T), respectively. For two distinct vertices u, v of T, let $P_T[u,v]$ denote the unique path in T connecting u and v. When $B(T) \ne \emptyset ,$ we call the graph $S_T = \bigcup _{u, v \in B(T)} P_T[u, v]$ the internal subtree of T. In this paper, we give two conditions for a connected graph to have a spanning tree whose internal subtree has few branch vertices and leaves. Moreover, the sharpness of our result is also shown.

1 Introduction

In this paper, we consider only simple graphs, which have neither loops nor multiple edges. Let G be a graph with vertex set V(G) and edge set E(G). For any vertex $u\in V(G)$, we use $N_G(u)$ and $\deg _G(u)$ to denote the set of neighbors of u and the degree of u in G, respectively. We define $G-uv$ to be the graph obtained from G by deleting the edge $uv\in E(G)$, and $G+uv$ to be the graph obtained from G by adding an edge uv between two non-adjacent vertices u and v of G.

Let $X\subseteq V(G)$. We denote by |X| the cardinality of X, $\deg _G(X)=\sum \nolimits _{x\in X}\deg _G(x)$, $N_G(X)=\bigcup _{x \in X} N_G(x)$ and $G-X$ is a subgraph of G which is obtained from G by deleting the vertices in X together with their incident edges. X is called an independent set of G if no two vertices of X are adjacent in G. For two vertices u and v of V(G), the distance between u and v in G denoted by $d_G(u, v)$. For an integer $m\geqslant 2,$ let $\alpha ^{m}(G)$ denote the number defined by

$$\begin{aligned} \alpha ^{m}(G)=\max \{ |S|:S\subseteq V(G),d_{G}(x,y)\geqslant m\,\ \forall x,y\in S, x\not = y\}. \end{aligned}$$

For two integers $m, p\geqslant 2$, we define

$$\begin{aligned} \sigma _p^{m}(G)=\min \{ \deg _G(S) : S\subseteq V(G), |S|=p,&\ d_{G}(x,y)\geqslant m\forall x, y\in S, x\not = y \}. \end{aligned}$$

For convenience, we define $\sigma ^{m}_{p}(G)=+\infty$ if $\alpha ^{m}(G)<p$. We note that $\alpha ^{2}(G)$ is often written $\alpha (G)$, which is the independence number of G,  and $\sigma _p^{2}(G)$ is often written $\sigma _{p}(G)$, which is the minimum degree sum of p independent vertices.

Let T be a tree. Vertices of degree one and vertices of degree at least three in T are its leaves and branch vertices, respectively. Let L(T) be the sets of leaves and B(T) be the sets of branch vertices of T. The subtree $T-L(T)$ of T is called the stem of T and is denoted by Stem(T). Many researchers have investigated independence number conditions and degree sum conditions for the existence of spanning trees whose stem has few leaves or branch vertices. Below, we list two results on this topic.

Theorem 1

(Kano and Yan 2014) Let G be a connected graph and let $k\geqslant 2$ be an integer. If either $\alpha ^{4}(G)\leqslant k$ or $\sigma _{k+1}(G)\geqslant |G|-k-1$, then G has a spanning tree whose stem has at most k leaves.

Theorem 2

(Yan 2016) Let G be a connected graph and $k \geqslant 0$ be an integer. If one of the following conditions holds, then G has a spanning tree whose stem has at most k branch vertices.

• (i) $\alpha ^{4}(G)\leqslant k+2,$

• (ii) $\sigma ^{4}_{k+3}(G)\geqslant |G|-2k-3.$

Fig. 1

Tree T and $S_T=R\_Stem(T)$

Let T be a tree with $B(T) \ne \emptyset$. For two distinct vertices u, v of T, let $P_T[u,v]$ denote the unique path in T connecting u and v. We call the graph $S_T = \bigcup _{u, v \in B(T)} P_T[u, v]$ the internal subtree of T (see Gould and Shull 2020). We describe the internal subtree differently as follows. For each $s\in L(T)$, let $a_s$ be the nearest branch vertex to s. We let $v_s$ be the unique vertex in $N_T(a_s)\cap P_T[s,a_s]$. The path that connects s to $v_s$ is called a leaf-branch path of T incident to s and denoted by $lbP_T(s)$. Then $S_T= T- \bigcup _{s \in L(T)} V(lbP_T(s))$ is also known as the reduced stem of T and denoted by $R\_Stem(T)$ (see Ha et al. 2021a, b) (see Fig.  for an example of T and $S_T=R\_Stem(T)$). A leaf of $S_T$ is called a peripheral branch vertex of T (see Maezawa et al. 2019; Saito and Sano 2016). In 2020, Ha et al. gave two conditions on connected graphs which ensures the existence of a spanning tree with few peripheral branch vertices. For each real number r, the notation $\lfloor r\rfloor$ stands for the biggest integer not exceeding r.

Theorem 3

(Ha et al. 2021a) Let G be a connected graph and $k\ge 2$ be an integer. If one of the following conditions holds, then G has a spanning tree with at most k peripheral branch vertices.

• (i) $\alpha (G) \le 2k+2,$

• (ii) $\sigma _{k+1}^4(G) \ge \left\lfloor \frac{\vert G \vert - k}{2}\right\rfloor .$

Recently, Ha et al. obtained the following result.

Theorem 4

(Ha et al. 2021b) Let G be a connected graph and $k\geqslant 2$ be an integer. If the following condition holds, then G has a spanning tree whose reduced stem has at most k branch vertices:

$$\begin{aligned} \sigma _{k+3}^4(G) \geqslant \bigg \lfloor \frac{\vert G \vert - 2k-4}{2}\bigg \rfloor +1. \end{aligned}$$

Lately, some results guaranteeing spanning trees with a bounded number of branch vertices and leaves have been obtained.

Theorem 5

(Nikoghosyan 2016; Saito and Sano 2016) Let $k\ge 2$ be an integer. If a connected graph G satisfies $\deg _G(x)+\deg _G(y)\ge |G|-k+1$ for every two nonadjacent vertices $x, y\in V(G)$, then G has a spanning tree T with $|L(T)|+|B(T)|\le k+1$.

Theorem 6

(Maezawa et al. 2019) Let $k\ge 2$ be an integer. Suppose that a connected graph G satisfies

$$\begin{aligned} \max \{\deg _G(x), \deg _G(y)\}\ge \dfrac{|G|-k+1}{2} \end{aligned}$$

for every two nonadjacent vertices $x, y\in V(G)$. Then G has a spanning tree T with $|L(T)|+|B(T)|\le k+1$.

In this paper, we give two sufficient conditions for a connected graph to have a spanning tree whose internal subtree has few branch vertices and leaves.

Theorem 7

Let $k\ge 0$ be an integer. Suppose that a connected graph G satisfies one of the following conditions:

• (i) $\alpha ^{4}(G)\leqslant k+2,$

• (ii) $\sigma _{k+3}^4(G) \geqslant \bigg \lfloor \frac{|G| - 2k-4}{2}\bigg \rfloor +1.$

Then G has a spanning tree whose internal subtree has at most $2k+3$ branch vertices and leaves.

Note that if a tree has m branch vertices, then the number of leaves is at least $m+2$. Therefore, from the result of Theorem 7 we get Theorem 4.

To the end this section, we construct an example to show that the condition of Theorem 7 is sharp.

Let $k \geqslant 0$ and $m\geqslant 1$ be two integers. Let $H_0,H_1,\ldots ,H_{k+2}$ and $P_0,P_1,\ldots ,$ $P_{k+2}$ be $2k+6$ disjoint copies of the complete graph $K_m$ of order m. Let $x_1, x_2,\ldots , x_{k+1}, y_0, y_1,\ldots , y_{k+2}$ be $2k+4$ vertices not contained in $H_0\cup H_1\cup \cdots \cup H_{k+2}\cup P_0\cup P_1\cup \cdots \cup P_{k+2}$. Join $y_i$ to all the vertices of $H_i \cup P_i$ for every $0 \leqslant i \leqslant k+2$. Adding two edges $x_1y_0, x_{k+1}y_{k+2}$ and join $x_i$ to $y_i$ for every $1 \leqslant i \leqslant k+1$. Let G denote the resulting graph (see Fig. ).

Fig. 2

Graph G

Then $|G|=(2k+6)m+2k+4$ and $\alpha ^4(G) = k+3.$ In addition, we have

$$\begin{aligned} \sigma _{k+3}^4 (G) = \displaystyle \sum _{i=1}^{k+3} \deg _{G}(s_i)=(k+3)m = \left\lfloor \frac{\vert G \vert - 2k-4}{2}\right\rfloor , \end{aligned}$$

where $s_i$ is any vertex of $P_i$ for every $0 \leqslant i \leqslant k+2$. But G has no a spanning tree whose internal subtree has at most $2k+3$ branch vertices and leaves. Thus, the condition in Theorem 7 is sharp.

2 Proof of Theorem 7

First of all, let us state the following useful lemma.

Lemma 1

Let T be a tree. Then the number of leaves in T is counted as follow

$$\begin{aligned} |L(T)|=\sum _{x\in B(T)}(\deg _{T}(x)-2)+2. \end{aligned}$$

Suppose that G has no spanning tree T such that $|L(S_T)|+|B(S_T)|\le 2k+3$. Choose some spanning tree T of G such that:

• (T1) $|B(S_T)|+|L(S_T)|$ is as small as possible.

• (T2) |L(T)| is as small as possible, subject to (T1).

• (T3) $|S_T|$ is as small as possible, subject to (T2).

According to Lemma 1, we have $|L(S_T)|\ge |B(S_T)|+2$. Combining with $|B(S_T)|+|L(S_T)|\ge 2k+4$, it follows that $|L(S_T)|\ge k+3\ge 3$. Thus, $|B(S_T)|\ge 1$. Put $\ell =|L(S_T)|$ and $L(S_T)=\{a_1, a_2, \ldots , a_{\ell }\}$. We have $\ell \ge k+3$.

By the definition of the internal subtree, we have the following proposition.

Proposition 1

For every $i\in \{1, 2, \ldots , \ell \}$, there exist at least two leaves T which are connected to $a_i$ by paths in T. Namely, T has at least two leaf-branch paths connecting $a_i$ to a leaf of T.

Proposition 2

For each $i\in \{1, 2, \ldots , \ell \}$, there exist two leaves $x_i, y_i$ of T such that $lbP_T(x_i)$ and $lbP_T(y_i)$ connect $x_i$ and $y_i$ to $a_i$, respectively, and $N_G(x_i)\cap (V(S_T)-\{a_i\})=\emptyset$ and $N_G(y_i)\cap (V(S_T)-\{a_i\})=\emptyset$.

Proof

Assume that there exists $i\in \{1, 2, \ldots , \ell \}$ for which the claim does not hold. Then every leaf-branch path $P_T[z_j, v_{z_j}] (1 \le j \le m)$ of $a_i$, except at most one such a path, satisfies $N_G(z_j) \cap (V(S_T)-\{a_i\}) \ne \emptyset$. For each $j\in \{1, 2, \ldots , m\}$, take a vertex $t_j \in N_G(z_j) \cap (S_T-\{a_i\})$. Then

$$\begin{aligned} T' = T + \{z_j t_j: 1 \le j \le m\}-\{a_i v_{z_j}: 1 \le j \le m\} \end{aligned}$$

is a spanning tree of G such that $|B(S_{T'})|\le |B(S_T)|$, $|L(S_{T'})|\le |L(S_T)|,$ $|L(T')|=|L(T)|$ and $|S_{T'}| < |S_T|,$ where $a_i$ is not a vertex of $S_{T'}.$ This gives a conflict with the conditions (T1) or (T3). Hence, Proposition 2 is proved. $\square$

For $1 \le i \le \ell$, let $x_i$ and $y_i$ be vertices defined as in Proposition 2 and let $U=\bigcup \nolimits _{1\le i\le \ell }\{x_i, y_i\}$.

Proposition 3

U is an independent set of G.

Proof

Suppose that there exist two vertices $s, t \in U$ such that $st \in E(G).$ Without lost of generality, we assume that $s=x_i$ for some $i\in \{1,2,\ldots ,\ell \}.$ We have $a_{x_i}=a_i$. Consider the tree $T'= T +x_it -a_iv_{x_i}.$ Then, $T'$ satisfies $B(S_{T'})\subseteq B(S_T)$. If $\deg _T(a_i)=3$, then $L(S_{T'})=L(S_T){\setminus } \{a_i\}$, this contradicts the condition (T1). If $\deg _T(a_i)\ge 4$, then $L(S_{T'})=L(S_T)$ and $L(T')=(L(T)\cup \{v_{x_i}\}){\setminus } \{x_i, t\}$, which contradicts the condition (T2). Proposition 3 is proved. $\square$

Proposition 4

For any two distinct $i, j\in \{1, 2, \cdots , \ell \}$, $d_G(s_i, s_j)\ge 4$ for $s_i\in \{x_i, y_i\}$, $s_j\in \{x_j, y_j\}$.

Proof

For $u, v\in V(G)$, let $P_G(u, v)$ be a shortest path connecting u and v in G. Let $P_{ij}=P_G(s_i, s_j)$. We will prove $V(P_{ij})\cap (S_T\setminus \{a_i, a_j\})\not =\emptyset$. Indeed, assume that all vertices of $P_{ij}$ are contained in $(V(G)-S_T) \cup \{a_i,a_j\}$.

Let $t_i$ be the vertex of $lbP_T(s_i)\cap P_{ij}$ closest to $a_i$, and $t_j$ be the vertex of $lbP_T(s_j)\cap P_{ij}$ closest to $a_j$. Then $P_{ij}=P_G[s_i,t_i]\cup P_G[t_i,t_j]\cup P_G[t_j,s_j]$, where $P_G[t_i,t_j]$ passes through only vertices contained in $V(G)-V(S_T)$ (Fig. ).

Fig. 3

Distance between $s_i$ and $s_j$

For every vertex $p\in L(T)$ such that $lbP_T(p) \cap P_G[t_i,t_j] \ne \emptyset$, remove all the edges $a_pv_p$ of T and add $P_G[t_i,t_j]$. Furthermore, if the path $P_G[t_i, t_j]$ intersects an $lbP_T(p)$ multiple times, then for each cycle $(\omega )$ of $P_G[t_i, t_j]+lbP_T(p)$, we delete an edge of $E(\omega )\cap E(lbP_T(p))$ which associates with $V(P_G[t_i, t_j])$. Then the resulting subgraph $T'$ of G includes an unique cycle C which contains two vertices $a_i$ and $a_j$. Because $\vert B(S_T)\vert \geqslant 1,$ there exists a branch vertex u of $S_T$ to be contained in C. Let $x\in N_T(u)\cap V(C)$. Denote by $T''=T'-ux$. For every $p\in L(T)$ such that $lbP_T(p) \cap P_G[t_i,t_j] \ne \emptyset$, we have that for all vertices of $V(P_T[p, v_p])\setminus (V(P_T[p, v_p])\cap P_{ij})$ not contained in $S_{T''}$ and $B(S_{T''})=B(S_T)$ (if $\deg _T(u)\ge 4$) or $B(S_{T''})=B(S_T)\setminus \{u\}$ (if $\deg _T(u)=3$). Then $T''$ is a spanning tree of G satisfying the conditions $|B(S_{T''})|\le |B(S_T)|$ and $L(S_{T''})\subseteq ((S_T{\setminus } \{a_i, a_j\})\cup \{x\})$. This contradicts the condition (T1). Therefore, $P_{ij} \cap (S_T-\{a_i,a_j\})\not = \emptyset .$ Set $z \in P_{ij} \cap (S_T-\{a_i,a_j\}).$ Hence, by combining with Proposition 2, we obtain

$$\begin{aligned} d_G(s_i,s_j)=d_{P_{ij}}(s_i,s_j) = d_{P_{ij}}(s_i,z) +d_{P_{ij}}(z,s_j) \geqslant 2 + 2= 4. \end{aligned}$$

Proposition 4 has been proven. $\square$

According to Proposition 4, we have $\alpha ^4(G)\ge \ell \ge k+3$, which implies that G must satisfy the condition (ii) of Theorem 7.

Next, we choose T to be a spanning tree of G satisfying

• (T4) $\sum \nolimits _{i=1}^{\ell } \left( |lbP_T(x_i)|+|lbP_T(y_i)|\right)$ is as large as possible subject to (T1)-(T3).

For $p\in L(T)$ and $x\in P_T[p, v_p]$, let $x^+=N_T(x)\cap P_T[x, a_p]$ and if $x\not =p$, let $x^-=N_T(x)\cap P_T[x, p]$.

Proposition 5

For each $p\in L(T)\setminus U$, we have $N_G(U)\cap lbP_T(p)=\emptyset$.

Proof

Suppose that $N_G(U)\cap lbP_T(p)\not =\emptyset$. There exists $t\in U$ and $x\in lbP_T(p)$ such that $xt\in E(G)$. Put $T'=T+xt-xx^+$. If $x=v_p$, then $B(S_{T'})\subseteq B(S_T)$, $L(S_{T'})\subseteq L(S_T)$ and $L(T')=L(T){\setminus } \{t\}$. It contradicts the condition (T1) or (T2). If $x\not = v_p$, then $B(S_{T'})=B(S_T)$, $L(S_{T'})=(L(S_T)\cup \{p\}){\setminus } \{t\}$, $L(T')=(L(T)\cup \{v_p\}){\setminus } \{t\}$ and $S_{T'}=S_T$. However, the condition (T4) is contradicted (p of $T'$ instead of t of T). The proof is complete. $\square$

Proposition 6

For any two distinct $i, j \in \{1,2,\ldots ,\ell \}$, $N_G(s_i) \cap lbP_T({s_j}) = \emptyset$ for $s_i\in \{x_i, y_i\}$ and $s_j\in \{x_j, y_j\}$.

Proof

Suppose the assertion of the claim is false. Then there exists a vertex $x \in N_G(s_i) \cap lbP_T({s_j})$. Set $T' = T + xs_i.$ Then $T'$ is a subgraph of G including a unique cycle C,  which contains both $a_i$ and $a_j$.

Since $|B(S_T)|\geqslant 1$, then, there exists a branch vertex u of $S_T$ contained in C. Let $z\in N_T(u)\cap V(C)$. Consider the tree $T''=T'-uz$. If $\deg _T(u)\ge 4$, then $B(S_T'')=B(S_T)$. If $\deg _T(u)=3$ then $u\notin B(S_{T''})$, so $B(S_{T''})=B(S_T)\setminus \{u\}$. Then $T''$ is a spanning tree of G satisfying $B(S_{T''}) \subseteq B(S_T)$ and $L(S_{T''})\subseteq (L(S_T)\setminus \{a_i,a_j\})\cup \{z\})$. This contradicts the condition (T1). So Proposition 6 is proved. $\square$

Proposition 7

For every $1 \leqslant i \leqslant \ell$ and $s_i\in \{x_i, y_i\}$, we have

$$\begin{aligned} \sum \limits _{y\in U}|N_G(y) \cap lbP_T({s_i}) | \leqslant \vert lbP_T({s_i}) \vert - 1. \end{aligned}$$

Proof

By the same role of $x_i$ and $y_i,$ we can only consider $s_i=x_i$. By Proposition 6, we conclude that

$$\begin{aligned} N_G(U) \cap lbP_T({x_i}) = N_G(\{x_i,y_i\}) \cap lbP_T({x_i}). \end{aligned}$$

$\square$

Claim 7.1

$v_{x_i} \notin N_G(y_i)$.

Indeed, assume that $v_{x_i}y_i\in E(G)$. Consider the tree $T'=T+y_i v_{x_i} - {a_iv_{x_i}}.$ Then, $T'$ is a spanning tree of G such that $|B(S_{T'})|\le |B(S_T)|, |L(S_{T'})| \le |L(S_T)|$ and $|L(T')| < |L(T)|.$ This contradicts either the condition (T1) or the condition (T2).

Claim 7.2

If $x \in N_G(y_i)\cap lbP_T({x_i})$, then $x^+ \notin N_G(x_i)$.

Suppose that there exists $x \in N_G(y_i)\cap lbP_T({x_i})$ such that $x^+ \in N_G(x_i)$. Set $T' = T+\{xy_i,x_ix^+\}-\{xx^+,a_iv_{x_i}\}$. Hence $T'$ is a spanning tree of G such that $|B(S_{T'})|\le |B(S_T)|, |L(S_{T'})| \le |L(S_T)|$ and $|L(T')| < |L(T)|.$ This contradicts either the condition (T1) or the condition (T2). Claim 7.2 holds.

By Claims 7.1, 7.2 and Propositions 3, 6, we conclude that $\{v_{x_i}\},$ $N_G(y_i) \cap lbP_T({x_i})$ and $\left( N_G(x_i) \cap lbP_T({x_i})\right) ^{-}=\{x^- \ | \ x\in N_G(x_i)\cap lbP_T(x_i)\}$ are pairwise disjoint subsets in $lbP_T({x_i})$. Then

$$\begin{aligned}&\sum _{y\in U}|N_G(y) \cap lbP_T({x_i}) |\\&\quad = | N_G(y_i) \cap lbP_T({x_i})|+| N_G(x_i) \cap lbP_T({x_i})|\\&\quad =| N_G(y_i) \cap lbP_T({x_i})|+| (N_G(x_i) \cap lbP_T({x_i}))^{-}| \leqslant |lbP_T({x_i})|-1. \end{aligned}$$

This completes the proof of Proposition 7.

By Propositions  2,  6 and  7, we obtain that

$$\begin{aligned} \deg _G(U)&= \displaystyle \sum _{i=1}^{\ell } \left( \deg _G(x_i)+\deg _G(y_i)\right) \\&\leqslant \displaystyle \sum _{i=1}^{\ell }\left( \vert lbP_T({x_i})\vert -1 \right) + \displaystyle \sum _{i=1}^{\ell } \left( \vert lbP_T({y_i})\vert -1 \right) + 2|\{a_1, a_2, \ldots , a_{\ell }\}|\\&= \displaystyle \sum _{i=1}^{\ell }\left( \vert lbP_T({x_i})\vert +\vert lbP_T({y_i})\vert \right) \\&= \vert G \vert - \vert S_T\vert -\sum \limits _{p\in L(T)\setminus U}|lbP_T(p)|\\&\leqslant \vert G \vert - \vert S_T\vert . \end{aligned}$$

On the other hand, we have $|S_T|\ge |L(S_T)|+|B(S_T)|\ge 2k+4$. So $\deg _G(U)\le |G|-2k-4$. It means that

$$\begin{aligned} \displaystyle \sum _{i=1}^{\ell } \deg _G(x_i) + \displaystyle \sum _{i=1}^{\ell } \deg _G(y_i) \leqslant |G| - 2k - 4. \end{aligned}$$

So

$$\begin{aligned} \min \left\{ \displaystyle \sum _{i=1}^{\ell } \deg _G(x_i),\displaystyle \sum _{i=1}^{\ell } \deg _G(y_i)\right\} \leqslant \dfrac{|G| - 2k - 4}{2}. \end{aligned}$$

Thus

$$\begin{aligned} \min \left\{ \displaystyle \sum _{i=1}^{\ell } \deg _G(x_i),\displaystyle \sum _{i=1}^{\ell } \deg _G(y_i)\right\} \leqslant \left\lfloor \dfrac{|G| - 2k - 4}{2}\right\rfloor . \end{aligned}$$

Combining the above inequality with Proposition 4 and $\ell \ge k+3$, we obtain

$$\begin{aligned} \sigma _{k+3}^4(G)\leqslant \sigma _{\ell }^4(G) \leqslant \min \left\{ \displaystyle \sum _{i=1}^{\ell } \deg _G(x_i), \displaystyle \sum _{i=1}^{\ell } \deg _G(y_i)\right\} \leqslant \left\lfloor \dfrac{|G| - 2k-4}{2}\right\rfloor . \end{aligned}$$

This contradicts the assumption (ii) of Theorem 7. The proof of Theorem 7 is completed. $\square$