Article in press
Authors:
Title:
Sufficient conditions for spanning trees with constrained leaf distance in a graph
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-06-06 , Revised: 2023-10-30 , Accepted: 2023-11-04 , Available online: 2023-11-21 , https://doi.org/10.7151/dmgt.2530
Abstract:
The leaf distance of a tree is the minimum of distances between any
two leaves of a tree. It is well known that seeking sufficient
conditions for a graph to have some special kinds of spanning trees
is an interesting and popular problem. In this paper, we first
provide a lower bound on the size of a graph $G$ to guarantee that
$G$ has a spanning tree with leaf distance at least $4$.
Moreover, for any graph $G$ with minimum degree $\delta$, we also
deduce a lower bound on the spectral radius (or the signless
Laplacian spectral radius) of $G$ to ensure the existence of a
spanning tree with leaf distance of at least $4$ in $G$.
Keywords:
spanning tree, leaf distance, (signless Laplacian) spectral radius
References:
- G. Ao, R. Liu and J. Yuan, Spectral radius and spanning trees of graphs, Discrete Math. 346(8) (2023) 113400.
https://doi.org/10.1016/j.disc.2023.113400 - J. Akiyama and M. Kano, Factors and Factorizations of Graphs: Proof Techniques in Factor Theory, Lecture Notes in Math. 2031 (Springer, Berlin Heidelberg, 2011).
https://doi.org/10.1007/978-3-642-21919-1 - R. Bapat, Graphs and Matrices (Springer, London, 2010).
https://doi.org/10.1007/978-1-84882-981-7 - J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (The Macmillan, Press Ltd., London, 1976).
- D. Fan, S. Goryainov, X. Huang and H. Lin, The spanning $k$-trees, perfect matchings and spectral radius of graphs, Linear Multilinear Algebra 70 (2022) 7264–7275.
https://doi.org/10.1080/03081087.2021.1985055 - A. Kaneko, Spanning trees with constraints on the leaf degree, Discrete Appl. Math. 115 (2001) 73–76.
https://doi.org/10.1016/S0166-218X(01)00216-5 - A. Kaneko, M. Kano and K. Suzuki, Spanning trees with leaf distance at least four, J. Graph Theory 55 (2007) 83–90.
https://doi.org/10.1002/jgt.20221 - S. O, Spectral radius and matchings in graphs, Linear Algebra Appl. 614 (2021) 316–324.
https://doi.org/10.1016/j.laa.2020.06.004 - K. Ozeki and T. Yamashita, Spanning trees: A survey, Graphs Combin. 27 (2011) 1–26.
https://doi.org/10.1007/s00373-010-0973-2 - S. Win, On a conjecture of Las Vergnas concerning certain spanning trees in graphs, Results Math. 2 (1979) 215–224.
https://doi.org/10.1007/BF03322958 - S. Win, On a connection between the existence of $k$-trees and the toughness of a graph, Graphs Combin. 5 (1989) 201–205.
https://doi.org/10.1007/BF01788671 - L. You, M. Yang, W. So and W. Xi, On the spectrum of an equitable quotient matrix and its application, Linear Algebra Appl. 577 (2019) 21–40.
https://doi.org/10.1016/j.laa.2019.04.013 - J. Zheng, X. Huang and J. Wang, Spectral condition for spanning $k$-ended trees in $t$-connected graphs (2023).
arXiv: 2305.04211.pdf
Close