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.
  • Received: 2016-09-29.
  • Revised: 2016-12-13.
  • Accepted: 2017-01-03.
  • Published online: 2017-04-28.
Opuscula Mathematica - cover

Cite this article as:
Junqing Cai, Evelyne Flandrin, Hao Li, Qiang Sun, Spanning trees with a bounded number of leaves, Opuscula Math. 37, no. 4 (2017), 501-508, http://dx.doi.org/10.7494/OpMath.2017.37.4.501

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.