The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree

Jonathan Cutler, A. J. Radcliffe

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

In this article, we make progress on a question related to one of Galvin that has attracted substantial attention recently. The question is that of determining among all graphs G with n vertices and Δ(G) ≤ r, which has the most complete subgraphs of size t, for t≥3. The conjectured extremal graph is aKr+1 ∪ Kb, where n = a(r + 1) + b with 0 ≤ b ≤ r. Gan et al. (Combin Probab Comput 24(3) (2015), 521–527) proved the conjecture when a ≤ 1, and also reduced the general conjecture to the case t = 3. We prove the conjecture for r ≤ 6 and also establish a weaker form of the conjecture for all r.

Original languageEnglish
Pages (from-to)134-145
Number of pages12
JournalJournal of Graph Theory
Volume84
Issue number2
DOIs
StatePublished - 1 Feb 2017

Fingerprint

Maximum Degree
Subgraph
Graph in graph theory
Extremal Graphs

Keywords

  • cliques
  • complete subgraphs
  • independent sets

Cite this

@article{6f65a3af5b7445399e20ce8ebac30406,
title = "The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree",
abstract = "In this article, we make progress on a question related to one of Galvin that has attracted substantial attention recently. The question is that of determining among all graphs G with n vertices and Δ(G) ≤ r, which has the most complete subgraphs of size t, for t≥3. The conjectured extremal graph is aKr+1 ∪ Kb, where n = a(r + 1) + b with 0 ≤ b ≤ r. Gan et al. (Combin Probab Comput 24(3) (2015), 521–527) proved the conjecture when a ≤ 1, and also reduced the general conjecture to the case t = 3. We prove the conjecture for r ≤ 6 and also establish a weaker form of the conjecture for all r.",
keywords = "cliques, complete subgraphs, independent sets",
author = "Jonathan Cutler and Radcliffe, {A. J.}",
year = "2017",
month = "2",
day = "1",
doi = "10.1002/jgt.22016",
language = "English",
volume = "84",
pages = "134--145",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",
number = "2",

}

The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree. / Cutler, Jonathan; Radcliffe, A. J.

In: Journal of Graph Theory, Vol. 84, No. 2, 01.02.2017, p. 134-145.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree

AU - Cutler, Jonathan

AU - Radcliffe, A. J.

PY - 2017/2/1

Y1 - 2017/2/1

N2 - In this article, we make progress on a question related to one of Galvin that has attracted substantial attention recently. The question is that of determining among all graphs G with n vertices and Δ(G) ≤ r, which has the most complete subgraphs of size t, for t≥3. The conjectured extremal graph is aKr+1 ∪ Kb, where n = a(r + 1) + b with 0 ≤ b ≤ r. Gan et al. (Combin Probab Comput 24(3) (2015), 521–527) proved the conjecture when a ≤ 1, and also reduced the general conjecture to the case t = 3. We prove the conjecture for r ≤ 6 and also establish a weaker form of the conjecture for all r.

AB - In this article, we make progress on a question related to one of Galvin that has attracted substantial attention recently. The question is that of determining among all graphs G with n vertices and Δ(G) ≤ r, which has the most complete subgraphs of size t, for t≥3. The conjectured extremal graph is aKr+1 ∪ Kb, where n = a(r + 1) + b with 0 ≤ b ≤ r. Gan et al. (Combin Probab Comput 24(3) (2015), 521–527) proved the conjecture when a ≤ 1, and also reduced the general conjecture to the case t = 3. We prove the conjecture for r ≤ 6 and also establish a weaker form of the conjecture for all r.

KW - cliques

KW - complete subgraphs

KW - independent sets

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

U2 - 10.1002/jgt.22016

DO - 10.1002/jgt.22016

M3 - Article

AN - SCOPUS:84959214377

VL - 84

SP - 134

EP - 145

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 2

ER -