Spanning trees with a bounded number of leaves

• Autorzy: Cai J. , Flandrin E. , Li H. , Sun Q.

Identyfikatory

DOI

10.7494/OpMath.2017.37.4.501

• Języki publikacji: EN

Abstrakty

EN

n 1998, H. Broersma and H. Tuinstra proved that: Given a connected graph G with n ≥ 3 vertices, if d(u) + d(y) ≥n — k + 1 for all non-adjacent vertices u and v of G (k ≥ 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≤ t ≤k) independent vertices and we prove what follows: Let G be a connected graph on n ≥ 3 vertices and k ≥ 2 be an integer. If the implicit degree sum of any t independent vertices is at least [formula] for (k≥ t ≥ 2), then G has a spanning tree with at most k leaves.

Słowa kluczowe

EN

spanning tree; implicit degree; leaves

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2017
• Tom: Vol. 37, no. 4
• Strony: 501--508
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Cai J.

• Qufu Normal University School of Management Rizhao, 276826, P.R. China
• LRI, UMR 6823 CNRS and Universite Paris-Saclay B.650, 91405 Orsay Cedex, France

autor

Flandrin E.

• LRI, UMR 6823 CNRS and Universite Paris-Saclay B.650, 91405 Orsay Cedex, France

autor

Li H.

• LRI, UMR 6823 CNRS and Universite Paris-Saclay B.650, 91405 Orsay Cedex, France
• Jianghan University Institute for Interdisciplinary Research 430056 Wuhan, P.R. China

autor

Sun Q.

• LRI, UMR 6823 CNRS and Universite Paris-Saclay B.650, 91405 Orsay Cedex, France

Bibliografia

• [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. Ryjaceck, 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.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).