Name
Abstract | ||
|---|---|---|
Let i(t)(G) be the number of independent sets of size t in a graph G. Engbers and Galvin asked how large i(t)(G) could be in graphs with minimum degree at least delta. They further conjectured that when n >= 2 delta and t >= 3, i(t)(G) is maximized by the complete bipartite graph K-delta,K-n-delta. This conjecture has recently drawn the attention of many researchers. In this short note, we prove this conjecture. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1017/S0963548314000546 | COMBINATORICS PROBABILITY & COMPUTING |
Field | DocType | Volume |
Discrete mathematics,Complete bipartite graph,Graph,Combinatorics,Conjecture,Mathematics | Journal | 24 |
Issue | ISSN | Citations |
3 | 0963-5483 | 3 |
PageRank | References | Authors |
0.50 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wenying Gan | 1 | 9 | 1.09 |
| Po-Shen Loh | 2 | 133 | 18.68 |
| Benny Sudakov | 3 | 1391 | 159.71 |