Spectral radius and spanning trees of graphs¹¹1Supported by National Natural Science Foundation of China (Nos. 11971445 and 12261032) and Natural Science Foundation of Henan Province (No. 202300410377).

In this paper, we consider simple, undirected and connected graphs. For undefined terms and notions, one can refer to [5] and [2]. Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. The order and size of $G$ are denoted by $|V(G)|=n$ and $|E(G)|=e(G)$, respectively. We denote by $d_{G}(v)$, $\omega(G)$, $i(G)$ and $\overline{G}$ the vertex $v$ of degree in $G$, the clique number, the number of isolated vertices and the complement of $G,$ respectively. We use $P_{n}$, $C_{n}$, $K_{n}$ and $K_{m,n}$ to denote the path of order $n$, the cycle of order $n$, the complete graph of order $n$, and the complete bipartite graph with bipartition $(X,Y)$, where $|X|=m$ and $|Y|=n$. Let $G_{1}$ and $G_{2}$ be two vertex-disjoint graphs. We denote by $G_{1}+G_{2}$ the disjoint union of $G_{1}$ and $G_{2}.$ The join $G_{1}\vee G_{2}$ is the graph obtained from $G_{1}+G_{2}$ by adding all possible edges between $V(G_{1})$ and $V(G_{2})$.

Let $A(G)$ and $D(G)$ be the adjacency matrix and diagonal degree matrix of $G$. Let $Q(G)=D(G)+A(G)$ be the signless Laplacian matrix of $G$. The largest eigenvalues of $A(G)$ and $Q(G)$, denoted by $\rho(G)$ and $q(G)$, are called the spectral radius and the signless Laplacian spectral radius of $G$, respectively. For convenience, Liu, Lai and Das [23] introduced the nonnegative matrix $A_{a}(G)=aD(G)+A(G)~{}(a\geq 0)$ of a graph $G$. The largest eigenvalue of $A_{a}(G)$ is called the $A_{a}$-spectral radius of $G$, denoted by $\rho_{a}(G)$. It is clear that $\rho_{0}(G)=\rho(G)$ and $\rho_{1}(G)=q(G).$

The concept of closure of a graph was used implicitly by Ore [25], and formally introduced by Bondy and Chvatal [4]. Fix an integer $l\geq 0$, the $l$-closure of a graph $G$ is the graph obtained from $G$ by successively joining pairs of nonadjacent vertices whose degree sum is at least $l$ until no such pair exists. Denote by $C_{l}(G)$ the $l$-closure of $G.$

For integer $k\geq 2,$ a spanning $k$-ended-tree of a connected graph $G$ is a spanning tree with at most $k$ leaves. Note that a spanning $2$-ended-tree is a Hamilton path. Hence a spanning $k$-ended-tree of a graph is a natural generalization of a Hamilton path. Fiedler and Nikiforov [14] initially proved sufficient conditions for a graph to contain a Hamilton path in terms of the spectral radius of a graph or its complement. Ning and Ge [20], Li and Ning [21] improved and extended results in [14]. As a special case of spanning $k$-ended-tree, there are many sufficient conditions to assure a graph to contain a Hamilton path (see for example [6, 22, 24, 28, 29]). In fact, a Hamilton path can also be generalized to a spanning $k$-tree. A spanning $k$-tree of a connected graph $G$ is a spanning tree in which every vertex has degree at most $k$, where $k\geq 2$ is an integer. Fan et al. [11] presented spectral conditions for the existence of a spanning $k$-tree in a connected graph.

Broersma and Tuinstra [3] showed that the problem of whether a given connected graph contains a spanning $k$-ended tree is NP-complete. Furthermore, they presented a degree sum condition to guarantee that a connected graph has a spanning $k$-ended tree.

Moreover, Broersma and Tuinstra [3] proved the following closure theorem for the existence of a spanning $k$-ended-tree, which is crucial to our proof.

Inspired by the work of Broersma and Tuinstra [3], we focus on the following interesting problem in this paper.

For more results on spanning $k$-ended-tree, one can refer to [7, 8, 9, 12, 18, 19, 26, 27]. Inspired by the ideas on Hamilton path from Li and Ning [21] and using typical spectral techniques, we prove tight spectral conditions to guarantee the existence of a spanning $k$-ended-tree in a connected graph. Let $R(n,s)$ be an $s$-regular graph with $n$ vertices.

Kaneko [17] introduced the concept of leaf degree of a spanning tree. Let $T$ be a spanning tree of a connected graph $G$. The leaf degree of a vertex $v\in V(T)$ is defined as the number of leaves adjacent to $v$ in $T$. Furthermore, the leaf degree of $T$ is the maximum leaf degree among all the vertices of $T$. They posed a necessary and sufficient condition for a connected graph to contain a spanning tree with leaf degree at most $k$. Let $i(G-S)$ denote the number of isolated vertices of $G-S.$

In this paper, we consider the following spectral extremal problem.

Motivated by Kaneko’s theorem, we present tight spectral conditions for the existence of a spanning tree with leaf degree at most $k$ in a connected graph.

Before presenting our main result, we first show that an $(n-1)$-closed connected graph $G$ must contain a large clique if its number of edges is large enough.

With the help of Lemma 2.1, we prove a technical sufficient condition in terms of $e(G)$ to assure that $G$ has a spanning $k$-ended-tree.

Next we will present important upper and lower bounds of $\rho(G)$ and $q(G)$ that will be used in our subsequent arguments.

Let $A=(a_{ij})$ and $B=(b_{ij})$ be two $n\times n$ matrices. Define $A\leq B$ if $a_{ij}\leq b_{ij}$ for all $i$ and $j$, and define $A<B$ if $A\leq B$ and $A\neq B$.

Now, we are in a position to present the proof of Theorem 1.3.

(ii) Let $G$ be a connected graph of order $n$ with $n\geq{\rm max}\{6k+5,\frac{3}{2}k^{2}+\frac{3}{2}k+2\}.$ Assume that $G$ has no a spanning $k$-ended-tree, where $k\geq 2$ is an integer. By Lemma 2.7, we have $q(K_{1}\vee(K_{n-k-1}+kK_{1}))>q(K_{n-k})=2(n-k-1).$ By Lemma 2.5 and the assumption, we have

We can deduce that $e(G)>\frac{[2(n-k-1)-n+2](n-1)}{2}\geq{n-k-1\choose 2}+k^{2}+k+1$ for $n\geq\frac{3}{2}k^{2}+\frac{3}{2}k+2$. Let $H=C_{n-1}(G)$. By Lemma 2.2, we have $H\cong K_{1}\vee(K_{n-k-1}+kK_{1})$. Since $G\subseteq H$, then

By the assumption, $q(G)\geq q(K_{1}\vee(K_{n-k-1}+kK_{1}))$, and hence $G\cong H$. Recall that $K_{1}\vee(K_{n-k-1}+kK_{1})$ has no a spanning $k$-ended-tree. Hence $G\cong K_{1}\vee(K_{n-k-1}+kK_{1}).$

(iii) Let $G$ be a connected graph of order $n$ and $k\geq 2$ be an integer. Let $H=C_{n-1}(G).$ If $H\cong K_{n},$ then $H$ has a spanning $k$-ended-tree. By Theorem 1.2, $G$ also has a spanning $k$-ended-tree, and the result follows. Next we always assume that $H\ncong K_{n}.$

Suppose to the contrary that $G$ has no a spanning $k$-ended-tree. By Theorem 1.2, $H$ has no a spanning $k$-ended-tree either. By Theorem 1.1, we have

for every pair of nonadjacent vertices $u$ and $v$ (always exists) of $H$. Then we have

for every edge $uv\in E(\overline{H})$. Notice that every non-trivial component of $\overline{H}$ has a vertex with the degree at least $\frac{n+k-2}{2}.$ Then its order is at least $\frac{n+k}{2}$, which implies that $\overline{H}$ has exactly one non-trivial component $F$ and $V(\overline{H}\backslash F)$ is the set of isolated vertices. Hence

for $uv\in E(F).$ Since $d_{H}(u)\geq d_{G}(u)\geq 1$ and $d_{H}(v)\geq d_{G}(v)\geq 1$, then we have $d_{F}(u)=d_{\overline{H}}(u)\leq n-2$ and $d_{F}(v)=d_{\overline{H}}(v)\leq n-2$. Hence $d_{F}(u)\geq n+k-2-d_{F}(v)\geq k$ and $d_{F}(v)\geq n+k-2-d_{F}(u)\geq k.$ That is, $k\leq d_{F}(u)\leq n-2$ and $k\leq d_{F}(v)\leq n-2$. It is easy to see that

Note that $f(d_{F}(u))$ is a convex function on $d_{F}(u)\in[k,n-2]$. Then

for every edge $uv\in E(\overline{H})$. By the assumption and Lemma 2.4, we have