This article is cited in 2 papers

On the number of independent sets in graphs with fixed independence number

A. B. Dainiak


Abstract: We construct a sequence of graphs of large degree with growing number of vertices for which the number of independent sets is substantially greater than the number of all subsets of the independent set of maximal cardinality.

UDC: 519.15

Received: 08.06.2006

DOI: 10.4213/dm20

 English version: Discrete Mathematics and Applications, 2007, 17:3, 249–252

Bibliographic databases:

• 
• 
• 
•