Maximizing the number of independent sets of a fixed size. (English) Zbl 1371.05213
Summary: Let \(i_t(G)\) be the number of independent sets of size \(t\) in a graph \(G\). J. Engbers and D. Galvin [J. Graph Theory 76, No. 2, 149–168 (2014; Zbl 1294.05121)] asked how large \(i_t(G)\) could be in graphs with minimum degree at least \(\delta\). They further conjectured that when \(n\geq 2\delta\) and \(t\geq 3\), \(i_t(G)\) is maximized by the complete bipartite graph \(K_{\delta,n-\delta}\). This conjecture has recently drawn the attention of many researchers. In this short note, we prove this conjecture.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C35 | Extremal problems in graph theory |
Citations:
Zbl 1294.05121References:
| [1] | Alexander, J., Cutler, J. and Mink, T. (2012) Independent sets in graphs with given minimum degree. Electron. J. Combin.19P37.2988859 · Zbl 1252.05157 |
| [2] | Alexander, J. and Mink, T. (2013) A new method for enumerating independent sets of a fixed size in general graphs. arXiv:1308.3242 · Zbl 1330.05115 |
| [3] | Cutler, J. and Radcliffe, A. J. (2013) The maximum number of complete subgraphs in a graph with given maximum degree. J. Combin. Theory Ser. B10460-71. · Zbl 1282.05073 |
| [4] | Engbers, J. and Galvin, D. (2014) Counting independent sets of a fixed size in graphs with a given minimum degree. J. Graph Theory76149-168. doi:10.1002/jgt.217563190271 · Zbl 1294.05121 |
| [5] | Galvin, D., Two problems on independent sets in graphs, Discrete Math., 311, 2105-2112, (2011) · Zbl 1228.05228 · doi:10.1016/j.disc.2011.06.015 |
| [6] | Kahn, J., An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput., 10, 219-237, (2001) · Zbl 0985.60088 |
| [7] | Katona, G. (1968) A theorem of finite sets. In Theory of Graphs: Proc. Colloq., Tihhany, 1966, Academic Press, pp. 187-207. · Zbl 0313.05003 |
| [8] | Kruskal, J. B. (1964) The number of simplices in a complex. In Mathematical Optimization Techniques (Bellman, R., ed.), University of California Press, pp. 251-278. · Zbl 0116.35102 |
| [9] | Law, H. and Mcdiarmid, C. (2013) On independent sets in graphs with given minimum degree. Combin. Probab. Comput.22874-884. doi:10.1017/S09635483130003693111547 · Zbl 1282.05181 |
| [10] | Lovász, L., Combinatorial Problems and Exercises, (2007), AMS · Zbl 1120.05001 |
| [11] | Sauvé, I. L., On chromatic graphs, Amer. Math. Monthly, 68, 107-111, (1961) · Zbl 0101.16702 · doi:10.2307/2312470 |
| [12] | Zhao, Y., The number of independent sets in a regular graph, Combin. Probab. Comput., 19, 109-112, (2010) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
