### 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 |

### Keywords

- cliques
- complete subgraphs
- independent sets

## Fingerprint Dive into the research topics of 'The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree'. Together they form a unique fingerprint.

## Cite this

Cutler, J., & Radcliffe, A. J. (2017). The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree.

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