An Extension of the Win Theorem: Counting the Number of Maximum Independent Sets

Abstract

Win proved a well-known result that the graph G of connectivity κ(G) with α(G) ≤ κ(G) + k − 1 (k ≥ 2) has a spanning k-ended tree, i.e., a spanning tree with at most k leaves. In this paper, the authors extended the Win theorem in case when κ(G) = 1 to the following: Let G be a simple connected graph of order large enough such that α(G) ≤ k + 1 (k ≥ 3) and such that the number of maximum independent sets of cardinality k + 1 is at most n − 2k − 2. Then G has a spanning k-ended tree.

Keywords

k-ended tree / Connectivity / Maximum independent set

References

[1] Ahmed, T., A survey on the Chvátal-Erdős theorem, https://doi.org/citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.9100&rep=repl&type=pdf

[2] Ainouche A. Common generalization of Chvátal-Erdős and Fraisse’s sufficient conditions for Hamiltonian graphs. Discrete Math., 1995, 142: 21-26

[3] Akiyama J, Kano M. Factors and Factorizations of Graphs: Proof Techniques in Factor Theory. Lecture Notes in Mathematics, 2011, Heidelberg: Springer-Verlag 2031

[4] Chen G, Hu Z, Wu Y. Circumferences of k-connected graphs involving independence numbers. J. Graph Theory, 2011, 68: 55-76

[5] Chen G, Li Y, Ma H An extension of the Chvátal-Erdős theorem: Counting the number of maximum independent sets. Graphs Combin, 2015, 31: 885-896

[6] Chvátal V, Erdős P. A note on Hamiltonian circuits. Discrete Math., 1972, 2: 111-113

[7] Enomoto H, Kaneko A, Saito A, Wei B. Long cycles in triangle-free graphs with prescribed independence number and connectivity. J. Combin. Theory Ser. B, 2004, 91: 43-55

[8] Han L, Lai L, Xiong H-J, Yan H. The Chvátal-Erdős condition for supereulerian graphs and the Hamiltonian index. Discrete Math., 2010, 310: 2082-2090

[9] Heuvel v d J. Extentions and consequences of Chvátal-Erdős theorem. Graphs Combin., 1996, 12: 231-237

[10] Jackson B, Oradaz O. Chvátal-Erdős conditions for paths and cycles in graphs and digraphs, A survey. Discrete Math., 1990, 84: 241-254

[11] Neumann-Lara V, Rivera-Campo E. Spanning trees with bounded degrees. Combinatorica, 1991, 11: 55-61

[12] Saito A. Chvátal-Erdős theorem —old theorem with new aspects. Lect. Notes Comput. Sci., 2008, 2535: 191-200

[13] West D B. Introduction to Graph Theory, 2001 2nd ed. Upper Saddle River: Prentice Hall

[14] Win S. On a conjecture of Las Vergnas concerning certain spanning trees in graphs. Results Math., 1979, 2: 215-224