Counting independent sets in cubic graphs of given girth

DOI10.1016/J.JCTB.2018.04.009zbMath1397.05133arXiv1611.01474OpenAlexW2963883188WikidataQ129188170 ScholiaQ129188170MaRDI QIDQ1791708

Guillem Perarnau, Will Perkins

Publication date: 11 October 2018

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

independent setsPetersen graphindependence polynomialhard-core modelHeawood graphoccupancy fraction

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (9)

On the number of sum-free triplets of sets ⋮ Extremal Regular Graphs: Independent Sets and Graph Homomorphisms ⋮ Maximizing the number of independent sets in claw-free cubic graphs ⋮ On the number of independent sets in uniform, regular, linear hypergraphs ⋮ A proof of the upper matching conjecture for large graphs ⋮ Independent vertex sets in the Zykov sum ⋮ Counting proper colourings in 4-regular graphs via the Potts model ⋮ Tight bounds on the coefficients of partition functions via stability ⋮ A reverse Sidorenko inequality

Cites Work

• The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph
• Independence in graphs with maximum degree four
• Minimizing the number of independent sets in triangle-free regular graphs
• The maximum number of complete subgraphs in a graph with given maximum degree
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• The Number of Independent Sets in a Regular Graph
• Some Ramsey-Type Numbers and the Independence Ratio
• Cages—a survey
• Extremal Regular Graphs: Independent Sets and Graph Homomorphisms
• On the average size of independent sets in triangle-free graphs
• On weighted graph homomorphisms
• Extremes of the internal energy of the Potts model on cubic graphs
• Independent sets, matchings, and occupancy fractions
• On the Widom–Rowlinson Occupancy Fraction in Regular Graphs

This page was built for publication: Counting independent sets in cubic graphs of given girth