Article in volume
Authors:
Title:
Spanning trees with a bounded number of branch vertices in a $K_{1,4}$-free graph
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 1195-1202
Received: 2020-02-01 , Revised: 2021-07-04 , Accepted: 2021-07-04 , Available online: 2021-08-13 , https://doi.org/10.7151/dmgt.2419
Abstract:
In 2008, it was conjectured that, for any positive integer $k$, a connected
$n$-vertex graph $G$ must contain a spanning tree with at most $k$ branch
vertices if $\sigma_{k+3}(G)\geq n-k$. In this paper, we resolve this conjecture
in the affirmative for the graphs $ K_ {1,4} $-free.
Keywords:
spanning tree, branch vertices, $K_{1,4}$-free
References:
- Y. Chen, P.H. Ha and D.D. Hanh, Spanning trees with at most $4$ leaves in $K_{1,5}$-free graphs, Discrete Math. 342 (2019) 2342–2349.
https://doi.org/10.1016/j.disc.2019.05.005 - E. Flandrin, T. Kaiser, R. Kužel, H. Li and Z. Ryjáček, Neighborhood unions and extremal spanning trees, Discrete Math. 308 (2008) 2343–2350.
https://doi.org/10.1016/j.disc.2007.04.071 - L. Gargano, M. Hammar, P. Hell, L. Stacho and U. Vaccaro, Spanning spiders and light-splitting switches, Discrete Math. 285 (2004) 83–95.
https://doi.org/10.1016/j.disc.2004.04.005 - R. Gould and W. Shull, On a conjecture on spanning trees with few branch vertices, J. Combin. Math. Combin. Comput. 108 (2019) 259–283.
- R. Gould and W. Shull, On spanning trees with few branch vertices, Discrete Math. 343 (2020) 111581.
https://doi.org/10.1016/j.disc.2019.06.037 - Z. Hu and P. Sun, Spanning $5$-ended trees in $K_{1,5}$-free graphs, Bull. Malays. Math. Sci. Soc. 43 (2020) 2565–2586.
https://doi.org/10.1007/s40840-019-00821-w - M. Kano, A. Kyaw, H. Matsuda, K. Ozeki, A. Saito and T. Yamashita, Spanning trees with a bounded number of leaves in a claw-free graph, Ars Combin. 103 (2012) 137–154.
- A. Kyaw, Spanning trees with at most $3$ leaves in $K_{1,4}$-free graphs, Discrete Math. 309 (2009) 6146–6148.
https://doi.org/10.1016/j.disc.2009.04.023 - A. Kyaw, Spanning trees with at most $k$ leaves in $K_{1,4}$-free graphs, Discrete Math. 311 (2011) 2135–2142.
https://doi.org/10.1016/j.disc.2011.06.025 - H. Matsuda, K. Ozeki and T. Yamashita, Spanning trees with a bounded number of branch vertices in a claw-free graph, Graphs Combin. 30 (2014) 429–437.
https://doi.org/10.1007/s00373-012-1277-5 - M.M. Matthews and D.P. Sumner, Longest paths and cycles in $K_{1,3}$-free graphs, J. Graph Theory 9 (1985) 269–277.
https://doi.org/10.1002/jgt.3190090208
Close