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

Jonathan Cutler, A. J. Radcliffe

Research output: Contribution to journalArticleResearchpeer-review

15 Citations (Scopus)

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

Fingerprint

Graph theory
Maximum Degree
Subgraph
Independent Set
Graph in graph theory
Regular Graph
Degree Condition
Extremal Problems
Minimum Degree
Substructure
Theorem
Enumeration
Covering
Regularity
Lower bound
Upper bound

Keywords

  • Complete subgraphs
  • Extremal enumeration
  • Independent sets

Cite this

@article{54ea09a6a2244270a159124a24a3b423,
title = "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 (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.",
keywords = "Complete subgraphs, Extremal enumeration, Independent sets",
author = "Jonathan Cutler and Radcliffe, {A. J.}",
year = "2014",
month = "1",
day = "1",
doi = "10.1016/j.jctb.2013.10.003",
language = "English",
volume = "104",
pages = "60--71",
journal = "Journal of Combinatorial Theory. Series B",
issn = "0095-8956",
publisher = "Academic Press Inc.",
number = "1",

}

The maximum number of complete subgraphs in a graph with given maximum degree. / Cutler, Jonathan; Radcliffe, A. J.

In: Journal of Combinatorial Theory. Series B, Vol. 104, No. 1, 01.01.2014, p. 60-71.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

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

AU - Cutler, Jonathan

AU - Radcliffe, A. J.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

KW - Complete subgraphs

KW - Extremal enumeration

KW - Independent sets

UR - http://www.scopus.com/inward/record.url?scp=84888380405&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2013.10.003

DO - 10.1016/j.jctb.2013.10.003

M3 - Article

VL - 104

SP - 60

EP - 71

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

IS - 1

ER -