The maximum number of complete subgraphs in a graph with given maximum degree

DOI10.1016/J.JCTB.2013.10.003zbMATH Open1282.05073arXiv1306.1803OpenAlexW2149047110MaRDI QIDQ2434716

A. J. Radcliffe, Jonathan Cutler

Publication date: 6 February 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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 $(2^{d+1}-1{)}^{n/2d}$ by the Kahn-Zhao theorem. Relaxing the regularity constraint to a minimum degree condition, Galvin conjectured that, for $ngeq2d$, the number of independent sets in a graph with $delta(G)geqd$ 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 $nleq2d$ as well. We find it convenient to address this problem from the perspective of $complementG$. In other words, we give an upper bound on the number of complete subgraphs of a graph $G$ on $n$ vertices with $Delta(G)leqr$, valid for all values of $n$ and $r$.

Full work available at URL: https://arxiv.org/abs/1306.1803

zbMATH Keywords

independent setscomplete subgraphsextremal enumeration

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Independent sets in graphs with given minimum degree
• Extremal problems for independent set enumeration
• Two problems on independent sets in graphs
• On the maximum number of cliques in a graph
• The maximum number of q-cliques in a graph with no p-clique
• A generalization of a theorem of Turán
• An entropy approach to the hard-core model on bipartite graphs
• The Number of Independent Sets in a Regular Graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Related Items (26)

Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs ⋮ Tree densities in sparse graph classes ⋮ Cliques in graphs excluding a complete graph minor ⋮ Extremal Regular Graphs: Independent Sets and Graph Homomorphisms ⋮ Maximizing the density of \(K_t\)'s in graphs of bounded degree and clique number ⋮ Homomorphisms into loop-threshold graphs ⋮ Many triangles with few edges ⋮ Minimizing the number of independent sets in triangle-free regular graphs ⋮ The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree ⋮ Many Cliques in Bounded-Degree Hypergraphs ⋮ Maximizing the Number of Independent Sets of a Fixed Size ⋮ Maximizing the number of independent sets in claw-free cubic graphs ⋮ Many cliques with few edges ⋮ Independent sets in graphs ⋮ Many cliques with few edges and bounded maximum degree ⋮ A proof of the upper matching conjecture for large graphs ⋮ On the number of \(r\)-matchings in a tree ⋮ Title not available (Why is that?) ⋮ Tight bounds on the coefficients of partition functions via stability ⋮ Counting independent sets in cubic graphs of given girth ⋮ Exact results on generalized Erdős-Gallai problems ⋮ Maximizing the number of \(H\)-colorings of graphs with a fixed minimum degree ⋮ Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree ⋮ The number of independent sets in an irregular graph ⋮ A reverse Sidorenko inequality ⋮ Extremal H‐Colorings of Graphs with Fixed Minimum Degree

This page was built for publication: The maximum number of complete subgraphs in a graph with given maximum degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2434716)