Geodesic
Spanning trees with a bounded number of branch vertices in a $K_{1,4}$-free graph
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1195-1202 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 σ_k+3(G)≥ 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 
@article{DMGT_2023_43_4_a16,
     author = {Hanh, Dang Dinh},
     title = {Spanning trees with a bounded number of branch vertices in a $K_{1,4}$-free graph},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1195--1202},
     year = {2023},
     volume = {43},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a16/}
}
TY  - JOUR
AU  - Hanh, Dang Dinh
TI  - Spanning trees with a bounded number of branch vertices in a $K_{1,4}$-free graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 1195
EP  - 1202
VL  - 43
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a16/
LA  - en
ID  - DMGT_2023_43_4_a16
ER  - 
%0 Journal Article
%A Hanh, Dang Dinh
%T Spanning trees with a bounded number of branch vertices in a $K_{1,4}$-free graph
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 1195-1202
%V 43
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a16/
%G en
%F DMGT_2023_43_4_a16
Hanh, Dang Dinh. Spanning trees with a bounded number of branch vertices in a $K_{1,4}$-free graph. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 1195-1202. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a16/

[1] Y. Chen, P.H. Ha and D.D. Hanh, Spanning trees with at most 4 leaves in K1,5-free graphs, Discrete Math. 342 (2019) 2342–2349. https://doi.org/10.1016/j.disc.2019.05.005

[2] 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

[3] 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

[4] R. Gould and W. Shull, On a conjecture on spanning trees with few branch vertices, J. Combin. Math. Combin. Comput. 108 (2019) 259–283.

[5] 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

[6] Z. Hu and P. Sun, Spanning 5-ended trees in K1,5-free graphs, Bull. Malays. Math. Sci. Soc. 43 (2020) 2565–2586. https://doi.org/10.1007/s40840-019-00821-w

[7] 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.

[8] A. Kyaw, Spanning trees with at most 3 leaves in K1,4-free graphs, Discrete Math. 309 (2009) 6146–6148. https://doi.org/10.1016/j.disc.2009.04.023

[9] A. Kyaw, Spanning trees with at most k leaves in K1,4-free graphs, Discrete Math. 311 (2011) 2135–2142. https://doi.org/10.1016/j.disc.2011.06.025

[10] 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

[11] M.M. Matthews and D.P. Sumner, Longest paths and cycles in K1,3-free graphs, J. Graph Theory 9 (1985) 269–277. https://doi.org/10.1002/jgt.3190090208