TY - JOUR

T1 - An Extension of the Chvátal–Erdős Theorem

T2 - Counting the Number of Maximum Independent Sets

AU - Chen, Guantao

AU - Li, Yinkui

AU - Ma, Haicheng

AU - Wu, Tingzeng

AU - Xiong, Liming

N1 - Publisher Copyright:
© 2014, Springer Japan.

PY - 2015/7/19

Y1 - 2015/7/19

N2 - Chvátal and Erdős proved a well-known result that the graph $$G$$G with connectivity $$\kappa (G)$$κ(G) not less than its independence number $$\alpha (G)$$α(G) [$$\alpha (G)+1$$α(G)+1, $$\alpha (G)-1$$α(G)-1, respectively] is Hamiltonian (traceable, Hamiltonian-connected, respectively). In this paper, we strengthen the Chvátal–Erdős theorem to the following: Let $$G$$G be a simple 2-connected graph of order large enough such that $$\alpha (G)\le \kappa (G)+1$$α(G)≤κ(G)+1 [$$\alpha (G)\le \kappa (G)+2$$α(G)≤κ(G)+2, $$\alpha (G)\le \kappa (G),$$α(G)≤κ(G), respectively] and such that the number of maximum independent sets of cardinality $$\kappa (G)+1$$κ(G)+1 [$$\kappa (G)+2$$κ(G)+2, $$\kappa (G)$$κ(G), respectively] is at most $$n-2\kappa (G)$$n-2κ(G) [$$n-2\kappa (G)-1$$n-2κ(G)-1, $$n-2\kappa (G)+1$$n-2κ(G)+1, respectively]. Then $$G$$G is either Hamiltonian (traceable, Hamiltonian-connected, respectively) or a subgraph of $$K_{k}+((kK_1)\cup K_{n-2k})$$Kk+((kK1)∪Kn-2k) [$$K_{k}+((k+1)K_1\cup K_{n-2k-1})$$Kk+((k+1)K1∪Kn-2k-1), $$K_{k}+((k-1)K_1\cup K_{n-2k+1})$$Kk+((k-1)K1∪Kn-2k+1), respectively].

AB - Chvátal and Erdős proved a well-known result that the graph $$G$$G with connectivity $$\kappa (G)$$κ(G) not less than its independence number $$\alpha (G)$$α(G) [$$\alpha (G)+1$$α(G)+1, $$\alpha (G)-1$$α(G)-1, respectively] is Hamiltonian (traceable, Hamiltonian-connected, respectively). In this paper, we strengthen the Chvátal–Erdős theorem to the following: Let $$G$$G be a simple 2-connected graph of order large enough such that $$\alpha (G)\le \kappa (G)+1$$α(G)≤κ(G)+1 [$$\alpha (G)\le \kappa (G)+2$$α(G)≤κ(G)+2, $$\alpha (G)\le \kappa (G),$$α(G)≤κ(G), respectively] and such that the number of maximum independent sets of cardinality $$\kappa (G)+1$$κ(G)+1 [$$\kappa (G)+2$$κ(G)+2, $$\kappa (G)$$κ(G), respectively] is at most $$n-2\kappa (G)$$n-2κ(G) [$$n-2\kappa (G)-1$$n-2κ(G)-1, $$n-2\kappa (G)+1$$n-2κ(G)+1, respectively]. Then $$G$$G is either Hamiltonian (traceable, Hamiltonian-connected, respectively) or a subgraph of $$K_{k}+((kK_1)\cup K_{n-2k})$$Kk+((kK1)∪Kn-2k) [$$K_{k}+((k+1)K_1\cup K_{n-2k-1})$$Kk+((k+1)K1∪Kn-2k-1), $$K_{k}+((k-1)K_1\cup K_{n-2k+1})$$Kk+((k-1)K1∪Kn-2k+1), respectively].

KW - Chvátal–Erdős theorem

KW - Connectivity

KW - Independence number

KW - Maximum independent set

UR - http://www.scopus.com/inward/record.url?scp=84931565424&partnerID=8YFLogxK

U2 - 10.1007/s00373-014-1416-2

DO - 10.1007/s00373-014-1416-2

M3 - Article

AN - SCOPUS:84931565424

SN - 0911-0119

VL - 31

SP - 885

EP - 896

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 4

ER -