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

DOI10.1016/j.jctb.2013.10.003zbMath1282.05073arXiv1306.1803OpenAlexW2149047110MaRDI QIDQ2434716

Andrew John Radcliffe, Jonathan Cutler

Publication date: 6 February 2014

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

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)

Related Items

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, Tight bounds on the coefficients of partition functions via stability, Counting independent sets in cubic graphs of given girth, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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