Two problems on independent sets in graphs

DOI10.1016/j.disc.2011.06.015zbMath1228.05228arXiv1206.3206OpenAlexW2144467924MaRDI QIDQ641174

David Galvin

Publication date: 21 October 2011

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

random graphindependent set polynomialstable set polynomialunimodal sequenceindependent set sequencelog concave sequence

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (21)

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 ⋮ On graph entropy measures based on the number of independent sets and matchings ⋮ Maximizing the density of \(K_t\)'s in graphs of bounded degree and clique number ⋮ Homomorphisms into loop-threshold graphs ⋮ 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 ⋮ The maximum number of complete subgraphs in a graph with given maximum degree ⋮ The independent set sequence of regular bipartite graphs ⋮ Many cliques with few edges ⋮ Maximum number of fixed points in AND-OR-NOT networks ⋮ On Independent Sets in Graphs with Given Minimum Degree ⋮ Independent sets in graphs ⋮ Many cliques with few edges and bounded maximum degree ⋮ Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree ⋮ Extremal H‐Colorings of Graphs with Fixed Minimum Degree ⋮ On the independence polynomial of the corona of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The independent set sequence of regular bipartite graphs
• The roots of the independence polynomial of a clawfree graph
• A sharp upper bound for the number of stable sets in graphs with given number of cut edges
• An upper bound for the number of independent sets in regular graphs
• Limit distribution for the existence of Hamiltonian cycles in random bipartite graphs
• The choice number of random bipartite graphs
• On the numbers of independent \(k\)-sets in a claw free graph
• Bounds on the number of vertex independent sets in a graph
• Theory of monomer-dimer systems
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• The Number of Independent Sets in a Regular Graph
• Extremal graphs for homomorphisms

This page was built for publication: Two problems on independent sets in graphs