Opuscula Math. 37, no. 4 (2017), 501-508
http://dx.doi.org/10.7494/OpMath.2017.37.4.501

Opuscula Mathematica

Spanning trees with a bounded number of leaves

Junqing Cai
Evelyne Flandrin
Hao Li
Qiang Sun

Abstract. In 1998, H. Broersma and H. Tuinstra proved that: Given a connected graph $$G$$ with $$n\geq 3$$ vertices, if $$d(u)+d(v)\geq n-k+1$$ for all non-adjacent vertices $$u$$ and $$v$$ of $$G$$ ($$k\geq 1$$), then $$G$$ has a spanning tree with at most $$k$$ leaves. In this paper, we generalize this result by using implicit degree sum condition of $$t$$ ($$2\leq t\leq k$$) independent vertices and we prove what follows: Let $$G$$ be a connected graph on $$n\geq 3$$ vertices and $$k\geq 2$$ be an integer. If the implicit degree sum of any $$t$$ independent vertices is at least $$\frac{t(n-k)}{2}+1$$ for ($$k\geq t\geq 2$$), then $$G$$ has a spanning tree with at most $$k$$ leaves.

Keywords: spanning tree, implicit degree, leaves.

Mathematics Subject Classification: 05C07.

Full text (pdf)

1. A. Ainouche, An improvement of Fraisse's sufficient condition for hamiltonian graphs, J. Graph Theory 16 (1992), 529-543.
2. J.A. Bondy, U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, New York, 2008.
3. H. Broersma, H. Tuinstra, Independent trees and Hamilton cycles, J. Graph Theory 29 (1998), 227-237.
4. J. Cai, H. Li, Hamilton cycles in implicit 2-heavy graphs, Graphs Combin. 32 (2016), 1329-1337.
5. J. Cai, H. Li, Y. Zhang, Fan-type implicit-heavy subgraphs for hamiltonicity of implicit claw-heavy graphs, Inform. Process. Lett. 116 (2016), 668-673.
6. G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory Ser. B 37 (1984), 221-227.
7. E. Flandrin, T. Kaiser, R. Kužel, H. Li, Z. Ryjáčeck, Neighborhood unions and extremal spanning trees, Discrete Math. 308 (2008), 2343-2350.
8. P. Fraisse, H. Jung, Longest cycles and independent sets in $$k$$-connected graphs, [in:] V.R. Kulli (ed.), Recent Studies in Graph Theory (Vischwa Internat. Publ. Gulbarga, India), 1989, 114-139.
9. H. Li, Generalizations of Dirac's theorem in Hamiltonian graph theory - a survey, Discrete Math. 313 (2013), 2034-2053.
10. H. Li, Y. Zhu, Cyclable sets of vertices in 3-connected graphs, J. Comb. 7 (2016), 495-508.
11. B. Wei, Longest cycles in 3-connected graphs, Discrete Math. 170 (1997), 195-201.
12. Y. Zhu, H. Li, X. Deng, Implicit-degrees and circumferences, Graphs Combin. 5 (1989) 283-290.
• Junqing Cai
• Qufu Normal University, School of Management, Rizhao, 276826, P.R. China
• LRI, UMR 6823 CNRS and Université Paris-Saclay, B.650, 91405 Orsay Cedex, France
• Evelyne Flandrin
• LRI, UMR 6823 CNRS and Université Paris-Saclay, B.650, 91405 Orsay Cedex, France
• Hao Li
• LRI, UMR 6823 CNRS and Université Paris-Saclay, B.650, 91405 Orsay Cedex, France
• Jianghan University, Institute for Interdisciplinary Research, 430056 Wuhan, P. R. China
• Qiang Sun
• LRI, UMR 6823 CNRS and Université Paris-Saclay, B.650, 91405 Orsay Cedex, France
• Communicated by Gyula O.H. Katona.
• Revised: 2016-12-13.
• Accepted: 2017-01-03.
• Published online: 2017-04-28.