### 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 aK_{r+1} ∪ K_{b}, 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 language | English |
---|---|

Pages (from-to) | 134-145 |

Number of pages | 12 |

Journal | Journal of Graph Theory |

Volume | 84 |

Issue number | 2 |

DOIs | |

State | Published - 1 Feb 2017 |

### Fingerprint

### Keywords

- cliques
- complete subgraphs
- independent sets

### Cite this

*Journal of Graph Theory*,

*84*(2), 134-145. https://doi.org/10.1002/jgt.22016

}

*Journal of Graph Theory*, vol. 84, no. 2, pp. 134-145. https://doi.org/10.1002/jgt.22016

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

Research output: Contribution to journal › Article › Research › peer-review

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

VL - 84

SP - 134

EP - 145

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 2

ER -