An Extension of the Chvatal-ErdAs Theorem: Counting the Number of Maximum Independent Sets

作者：Chen, Guantao; Li, Yinkui; Ma, Haicheng; Wu, Tingzeng; Xiong, Liming^*

来源：Graphs and Combinatorics, 2015, 31(4): 885-896.

DOI：10.1007/s00373-014-1416-2

• Chvatal-Erdos theorem
• Connectivity
• Independence number
• Maximum independent set

Chvatal and ErdAs proved a well-known result that the graph with connectivity not less than its independence number alpha(G) [alpha(G) + 1, alpha(G) - 1, respectively] is Hamiltonian (traceable, Hamiltonian-connected, respectively). In this paper, we strengthen the Chvatal-ErdAs theorem to the following: Let be a simple 2-connected graph of order large enough such that [, respectively] and such that the number of maximum independent sets of cardinality [, , respectively] is at most [, , respectively]. Then is either Hamiltonian (traceable, Hamiltonian-connected, respectively) or a subgraph of K-k + ((kK(1)) boolean OR K(n-2)k) [K-k + ((k + 1) K-1 boolean OR Kn-2k-1), K-k + ((k - 1) K-1 boolean OR Kn-2k+1), respectively].

• 出版日期2015-7
• 单位青海民族大学; 北京理工大学