The maximum number of complete subgraphs in a graph with given maximum degree

Abstract

Extremal problems involving the enumeration of graph substructures have a long history in graph theory. For example, the number of independent sets in a $d$-regular graph on $n$ vertices is at most $(2^{d+1}-1{)}^{n/2d}$ by the Kahn-Zhao theorem. Relaxing the regularity constraint to a minimum degree condition, Galvin conjectured that, for $n\ge 2d$, the number of independent sets in a graph with $\delta (G)\ge d$ is at most that in $K_{d,n-d}$. In this paper, we give a lower bound on the number of independent sets in a $d$-regular graph mirroring the upper bound in the Kahn-Zhao theorem. The main result of this paper is a proof of a strengthened form of Galvin's conjecture, covering the case $n\le 2d$ as well. We find it convenient to address this problem from the perspective of $\complement G$. In other words, we give an upper bound on the number of complete subgraphs of a graph $G$ on $n$ vertices with $\Delta (G)\le r$, valid for all values of $n$ and $r$.

14 pages

Cited by in corpus (1)

• Extremal H-colorings of graphs with fixed minimum degree