×

Counting independent sets of a fixed size in graphs with a given minimum degree. (English) Zbl 1294.05121

Summary: D. Galvin [Discrete Math. 311, No. 20, 2105–2112 (2011; Zbl 1228.05228)] 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 J. Alexander et al. [Electron. J. Comb. 19, No. 3, Research Paper P37, 11 p. (2012; Zbl 1252.05157)] who showed that for all triples \((n,\delta, t)\) with \(t\geq 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\leq 3\) and \(t\geq 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\geq 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.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C12 Distance in graphs
05C07 Vertex degrees
05C35 Extremal problems in graph theory

References:

[1] J.Alexander, J.Cutler, and T.Mink, Independent sets in graphs with given minimum degree, Electron J Combin19 (2012), \(\#\) P37. · Zbl 1252.05157
[2] N.Alon, Independent sets in regular graphs and sum‐free subsets of finite groups, Israel J Math73 (1991), 247-256. · Zbl 0762.05050
[3] T.Carroll, D.Galvin, and P.Tetali, Matchings and independent sets of a fixed size in regular graphs, J Combin Theory Series A116 (2009), 1219-1227. · Zbl 1243.05193
[4] J.Cutler and A. J.Radcliffe, Extremal problems for independent set enumeration, Electron J Combin18 (2011), \(\#\) P169. · Zbl 1229.05138
[5] J.Cutler and A. J.Radcliffe, Extremal graphs for homomorphisms, J Graph Theory67 (2011), 261-284. · Zbl 1231.05132
[6] J.Cutler and A. J.Radcliffe, The maximum number of complete subgraphs in a graph with given maximum degree, arXiv:1306.1803.
[7] D.Galvin, Two problems on independent sets in graphs, Discrete Math311 (2011), 2105-2112. · Zbl 1228.05228
[8] G.Hopkins and W.Staton, Some identities arising from the Fibonacci numbers of certain graphs, Fibonacci Quart22 (1984), 255-258. · Zbl 0548.05035
[9] H.Hua, A sharp upper bound for the number of stable sets in graphs with given number of cut edges, Appl Math Lett22 (2009), 1380-1385. · Zbl 1173.05333
[10] J.Kahn, An entropy approach to the hard‐core model on bipartite graphs, Combin Probab Comput10 (2001), 219-237. · Zbl 0985.60088
[11] C.Lin, and S.Lin, Trees and forests with large and small independent indices, Chinese J Math23 (1995), 199-210. · Zbl 0835.05020
[12] C.McDiarmid and H.‐F.Law, Independent sets in graphs with given minimum degree, arXiv:1210.1497.
[13] R.Merrifield and H.Simmons, Topological Methods in Chemistry, Wiley, New York, 1989.
[14] A.Pedersen and P.Vestergaard, Bounds on the number of vertex independent sets in a graph, Taiwanese J Math10 (2006), 1575-1587. · Zbl 1123.05068
[15] H.Prodinger and R.Tichy, Fibonacci numbers of graphs, Fibonacci Quart20 (1982), 16-21. · Zbl 0475.05046
[16] A. A.Sapozhenko, On the number of independent sets in bipartite graphs with large minimum degree, DIMACS Technical Report (2000), no. 2000-25.
[17] G.Wingard, Properties and applications of the Fibonacci polynomial of a graph, Ph.D. thesis, University of Mississippi, 1995.
[18] Y.Zhao, The number of independent sets in a regular graph, Combin Probab Comput19 (2010), 315-320. · Zbl 1215.05140
[19] A. A.Zykov, On some properties of linear complexes, Mat Sbornik N.S.24 (1949), 163-188. · Zbl 0033.02602
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.