Name
Abstract | ||
|---|---|---|
Galvin showed that for all fixed delta and sufficiently large n, the n-vertex graph with minimum degree delta that admits the most independent sets is the complete bipartite graph K delta,n-delta. 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,delta,t) with t >= 3, no n-vertex bipartite graph with minimum degree delta admits more independent sets of size t than K delta,n-delta. Here, we make further progress. We show that for all triples (n,delta,t) with delta <= 3 and t >= 3, no n-vertex graph with minimum degree delta admits more independent sets of size t than K delta,n-delta, and we obtain the same conclusion for delta>3 and t >= 2 delta+1. Our proofs lead us naturally to the study of an interesting family of critical graphs, namely those of minimum degree delta whose minimum degree drops on deletion of an edge or a vertex. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1002/jgt.21756 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
stable set,independent set,enumeration | Complete bipartite graph,Discrete mathematics,Topology,Circulant graph,Combinatorics,Line graph,Cubic graph,Bipartite graph,Independent set,Regular graph,Degree (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
76.0 | 2.0 | 0364-9024 |
Citations | PageRank | References |
4 | 0.57 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| John Engbers | 1 | 21 | 6.79 |
| David Galvin | 2 | 55 | 11.59 |