A result on spanning trees with bounded total excess

Abstract

Let $G$ be a connected graph and $T$ a spanning tree of $G$. Let $\rho (G)$ denote the adjacency spectral radius of $G$. The $k$-excess of a vertex $v$ in $T$ is defined as $\max \{0,d_T(v)-k\}$. The total $k$-excess $\mbox{te}(T,k)$ is defined by $\mbox{te}(T,k)=\sum\limits_{v\in V(T)}{\max\{0,d_T(v)-k\}}$. A tree $T$ is said to be a $k$-tree if $d_T(v)\le k$ for any $v\in V(T)$, that is to say, the maximum degree of a $k$-tree is at most $k$. In fact, $T$ is a spanning $k$-tree if and only if $\mbox{te}(T,k)=0$. This paper studies a generalization of spanning $k$-trees using a concept called total $k$-excess and proposes a lower bound for $\rho (G)$ in a connected graph $G$ to ensure that $G$ contains a spanning tree $T$ with $\mbox{te}(T,k)\leq b$, where $k$ and $b$ are two nonnegative integers with $k\ge \max \{5,b+3\}$ and $(b,k)\ne (2,5)$.

arXiv comment11 pages