{
  "id": "1405.1322",
  "version": "v1",
  "published": "2014-05-06T15:35:50.000Z",
  "updated": "2014-05-06T15:35:50.000Z",
  "title": "The maximum number of complete subgraphs of fixed size in a graph with given maximum degree",
  "authors": [
    "Jonathan Cutler",
    "A. J. Radcliffe"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "In this paper, 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 $\\Delta(G)\\leq r$, which has the most complete subgraphs of size $t$, for $t\\geq 3$. The conjectured extremal graph is $aK_{r+1}\\cup K_b$, where $n=a(r+1)+b$ with $0\\leq b\\leq r$. Gan, Loh, and Sudakov proved the conjecture when $a\\leq 1$, and also reduced the general conjecture to the case $t=3$. We prove the conjecture for $r\\leq 6$ and also establish a weaker form of the conjecture for all $r$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-05-06T15:35:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "complete subgraphs",
      "maximum number",
      "maximum degree",
      "fixed size",
      "attracted substantial attention"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1405.1322C"
    }
  }
}