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

Original language | English |
---|---|

Pages (from-to) | 60-71 |

Number of pages | 12 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 104 |

Issue number | 1 |

DOIs | |

State | Published - 1 Jan 2014 |

### Fingerprint

### Keywords

- Complete subgraphs
- Extremal enumeration
- Independent sets

### Cite this

*Journal of Combinatorial Theory. Series B*,

*104*(1), 60-71. https://doi.org/10.1016/j.jctb.2013.10.003

}

*Journal of Combinatorial Theory. Series B*, vol. 104, no. 1, pp. 60-71. https://doi.org/10.1016/j.jctb.2013.10.003

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

Research output: Contribution to journal › Article

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

AN - SCOPUS:84888380405

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 -