Extremal regular graphs: independent sets and graph homomorphisms

Abstract

This survey concerns regular graphs that are extremal with respect to the number of independent sets, and more generally, graph homomorphisms. More precisely, in the family of of $d$-regular graphs, which graph $G$ maximizes/minimizes the quantity $i(G{)}^{1/v(G)}$, the number of independent sets in $G$ normalized exponentially by the size of $G$? What if $i(G)$ is replaced by some other graph parameter? We review existing techniques, highlight some exciting recent developments, and discuss open problems and conjectures for future research.

Expository survey. Extended version

References in corpus (3)

• On the average size of independent sets in triangle-free graphs
• Extremes of the internal energy of the Potts model on cubic graphs
• Extremal regular graphs: the case of the infinite regular tree

Cited by in corpus (9)

• Extremes of the internal energy of the Potts model on cubic graphs
• The number of independent sets in an irregular graph
• Extremal regular graphs: the case of the infinite regular tree
• Counting proper colourings in 4-regular graphs via the Potts model
• Tight bounds on the coefficients of partition functions via stability
• Graph-indexed random walks on special classes of graphs
• Algorithmic aspects of $M$-Lipschitz mappings of graphs
• Toward a Nordhaus-Gaddum Inequality for the Number of Dominating Sets
• Independent Sets in n-vertex k-chromatic, \ell-connected graphs