Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree

DOI10.1002/jgt.21756zbMath1294.05121arXiv1204.3060OpenAlexW2125820980MaRDI QIDQ5418775

John Engbers, David Galvin

Publication date: 28 May 2014

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.3060

zbMATH Keywords

stable setenumerationindependent set

Mathematics Subject Classification ID

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

Related Items (18)

Tree densities in sparse graph classes ⋮ Cliques in graphs excluding a complete graph minor ⋮ A New Method for Enumerating Independent Sets of a Fixed Size in General Graphs ⋮ Complete subgraphs in connected graphs and its application to spectral moment ⋮ Maximizing the density of \(K_t\)'s in graphs of bounded degree and clique number ⋮ Homomorphisms into loop-threshold graphs ⋮ On supersaturation and stability for generalized Turán problems ⋮ Maximizing the number of independent sets of fixed size in Kn‐covered graphs ⋮ Many triangles with few edges ⋮ The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree ⋮ Maximizing the Number of Independent Sets of a Fixed Size ⋮ Many cliques with few edges ⋮ Extremal Graphs with Local Covering Conditions ⋮ Many cliques with few edges and bounded maximum degree ⋮ Independent sets in \(n\)-vertex \(k\)-chromatic \(\ell \)-connected graphs ⋮ Many H-Copies in Graphs with a Forbidden Tree ⋮ Extremal H‐Colorings of Graphs with Fixed Minimum Degree ⋮ Supersaturation for subgraph counts

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independent sets in graphs with given minimum degree
• Extremal problems for independent set enumeration
• Two problems on independent sets in graphs
• A sharp upper bound for the number of stable sets in graphs with given number of cut edges
• Matchings and independent sets of a fixed size in regular graphs
• Independent sets in regular graphs and sum-free subsets of finite groups
• Bounds on the number of vertex independent sets in a graph
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree
• The Number of Independent Sets in a Regular Graph
• Extremal graphs for homomorphisms

This page was built for publication: Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree