2024/12/01 by Wu, Jiancheng, Zhou, Sizhong, Liu, Hongxia · 2 citations
#05C05 #05C50 #05C70 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2412.00700
Let G be a graph and T be a spanning tree of G. We use Q(G)=D(G)+A(G) to denote the signless Laplacian matrix of G, where D(G) is the diagonal degree matrix of G and A(G) is the adjacency matrix of G. The signless Laplacian spectral radius of G is denoted by q(G). A necessary and sufficient condition for a connected bipartite graph G with bipartition (A,B) to have a spanning tree T with dT(v)≥ k for any v∈ A was independently obtained by Frank and Gyárfás (A. Frank, E. Gyárfás, How to orient the edges of a graph?, Colloq. Math. Soc. Janos Bolyai 18 (1976) 353--364), Kaneko and Yoshimoto (A. Kaneko, K. Yoshimoto, On spanning trees with restricted degrees, Inform. Process. Lett. 73 (2000) 163--165). Based on the above result, we establish a lower bound on the signless Laplacian spectral radius q(G) of a connected bipartite graph G with bipartition (A,B), in which the bound guarantees that G has a spanning tree T with dT(v)≥ k for any v∈ A.