Premium
Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree
Author(s) -
Engbers John,
Galvin David
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21756
Subject(s) - combinatorics , mathematics , bipartite graph , degree (music) , discrete mathematics , vertex (graph theory) , conjecture , graph , independent set , physics , acoustics
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 K δ , n − δ . 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 ( n , δ , t ) with t ≥ 3 , no n ‐vertex bipartite graph with minimum degree δ admits more independent sets of size t than K δ , n − δ . Here, we make further progress. We show that for all triples ( n , δ , t ) with δ ≤ 3 and t ≥ 3 , no n ‐vertex graph with minimum degree δ admits more independent sets of size t than K δ , n − δ , and we obtain the same conclusion for δ > 3 and t ≥ 2 δ + 1 . 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.