2025/07/06 by Ao, Guoyan, Liu, Ruifang, Yuan, Jinjiang
#FOS: Mathematics #Spectral Theory (math.SP)
paper · doi:10.48550/arxiv.2507.04400
Chvátal and Erdös [Discrete Math. 2 (1972) 111-113] stated that, for an m-connected graph G, if its independence number α(G)≤ m-1, then G is Hamilton-connected. Note that k-leaf-connectedness is a natural generalization of Hamilton-connectedness of a graph. Ozeki and Yamashita [Graphs Combin. 27 (2011) 1-26] posed an open problem: What is the sufficient condition based on the independence number for an m-connected graph to be k-leaf-connected? In this paper, we prove that if α(G)≤ m-k+1, then an m-connected graph G is k-leaf-connected. This not only answers the open problem of Ozeki and Yamashita, but also extends Chvátal-Erdös Theorem. As applications, we present sufficient spectral conditions for an m-connected graph to be k-leaf-connected. Let k≥ 2 be an integer and T be a spanning tree of a connected graph. The total k-excess te(T,k) is the summation of the k-excesses of all vertices in T, namely, te(T,k)=∑v∈ V(T)max\0, dT(v)-k\. One can see that T is a spanning k-tree if and only if te(T,k)=0. Fan, Goryainov, Huang and Lin [Linear Multilinear Algebra 70 (2022) 7264-7275] presented sufficient spectral conditions for a connected graph to contain a spanning k-tree. We in this paper propose sufficient conditions in terms of the spectral radius for a connected graph to contain a spanning tree with te(T,k)≤ b, where b≥0 is an integer.