2025/07/20 by Sizhong Zhou, Zhou, Sizhong
Mathematics · Computer Science · #Graph theory and applications #Interconnection Networks and Systems #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2507.15139
Let G be a connected graph and T a spanning tree of G. Let ρ(G) denote the adjacency spectral radius of G. The k-excess of a vertex v in T is defined as max\0,dT(v)-k\. The total k-excess te(T,k) is defined by te(T,k)=∑v∈ V(T)max\0,dT(v)-k\. A tree T is said to be a k-tree if dT(v)≤ k for any v∈ 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 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 ρ(G) in a connected graph G to ensure that G contains a spanning tree T with te(T,k)≤ b, where k and b are two nonnegative integers with k≥max\5,b+3\ and (b,k)≠(2,5).