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

Jonathan Cutler, A. J. Radcliffe

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

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 (2d+1-1)n/2d by the Kahn-Zhao theorem [7,13]. Relaxing the regularity constraint to a minimum degree condition, Galvin [5] conjectured that, for n≥2d, the number of independent sets in a graph with δ(G)≥d is at most that in Kd,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≤2d as well. We find it convenient to address this problem from the perspective of G-. From this perspective, we show that the number of complete subgraphs of a graph G on n vertices with δ(G)≤r, where n=a(r+1)+b with 0≤b≤r, is bounded above by the number of complete subgraphs in aKr+1∪Kb.

Original languageEnglish
Pages (from-to)60-71
Number of pages12
JournalJournal of Combinatorial Theory. Series B
Volume104
Issue number1
DOIs
StatePublished - 1 Jan 2014

Keywords

  • Complete subgraphs
  • Extremal enumeration
  • Independent sets

Fingerprint

Dive into the research topics of 'The maximum number of complete subgraphs in a graph with given maximum degree'. Together they form a unique fingerprint.

Cite this