An Extension of the Chvátal–Erdős Theorem: Counting the Number of Maximum Independent Sets

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].