Document Type

Article

Language

eng

Format of Original

20 p.

Publication Date

6-2014

Publisher

Wiley

Source Publication

Journal of Graph Theory

Source ISSN

0364-9024

Original Item ID

doi: 10.1002/jgt.21756

Abstract

Galvin showed that for all fixed δ and sufficiently large n, the n-vertex graph with minimum degree δ that admits the most independent sets is the complete bipartite graph . He conjectured that except perhaps for some small values of t, the same graph yields the maximum count of independent sets of size t for each possible t. Evidence for this conjecture was recently provided by Alexander, Cutler, and Mink, who showed that for all triples with , no n-vertex bipartite graph with minimum degree δ admits more independent sets of size t than . Here, we make further progress. We show that for all triples with and , no n-vertex graph with minimum degree δ admits more independent sets of size t than , and we obtain the same conclusion for and . Our proofs lead us naturally to the study of an interesting family of critical graphs, namely those of minimum degree δ whose minimum degree drops on deletion of an edge or a vertex.

Comments

Accepted version. Journal of Graph Theory, Vol. 76, No. 2 (June 2014): 149-168. DOI. © 2014 John Wiley and Sons. Used with permission.

Download

Share

COinS