1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Spanning Trees with a Bounded Number of Branch Vertices in a K1,4-Free Graph

Published Online: 05 Aug 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 01 Feb 2020
Accepted: 04 Jul 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 σk+3(G) ≥ nk. In this paper, we resolve this conjecture in the affirmative for the graphs K1,4-free.

Keywords

MSC 2010

[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.00510.1016/j.disc.2019.05.005Search in Google Scholar

[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.07110.1016/j.disc.2007.04.071Search in Google Scholar

[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.00510.1016/j.disc.2004.04.005Search in Google Scholar

[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.Search in Google Scholar

[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.03710.1016/j.disc.2019.06.037Search in Google Scholar

[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-w10.1007/s40840-019-00821-wSearch in Google Scholar

[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.Search in Google Scholar

[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.02310.1016/j.disc.2009.04.023Search in Google Scholar

[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.02510.1016/j.disc.2011.06.025Search in Google Scholar

[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-510.1007/s00373-012-1277-5Search in Google Scholar

[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.319009020810.1002/jgt.3190090208Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo