Many cliques with few edges

DOI10.37236/9550zbMATH Open1456.05080arXiv1912.09872OpenAlexW3130574724MaRDI QIDQ2223482FDOQ2223482

Authors: Rachel Kirsch, Andrew John Radcliffe 

Publication date: 29 January 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Recently Cutler and Radcliffe proved that the graph on $n$ vertices with maximum degree at most $r$ having the most cliques is a disjoint union of $lfloorn/(r+1)floor$ cliques of size $r+1$ together with a clique on the remainder of the vertices. It is very natural also to consider this question when the limiting resource is edges rather than vertices. In this paper we prove that among graphs with $m$ edges and maximum degree at most $r$, the graph that has the most cliques of size at least two is the disjoint union of $$ cliques of size $r+1$ together with the colex graph using the remainder of the edges.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Many triangles with few edges
• Many cliques with few edges and bounded maximum degree
• On the number of edge disjoint cliques in graphs of given size
• On the maximum number of cliques in a graph
• Many Cliques in Bounded-Degree Hypergraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Two problems on independent sets in graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The maximum number of complete subgraphs in a graph with given maximum degree
• Maximizing the Number of Independent Sets of a Fixed Size
• Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree
• Shadows of colored complexes.
• Face vectors of flag complexes
• Many \(T\) copies in \(H\)-free graphs
• The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree
• The maximum number of triangles in a graph of given maximum degree
• Many triangles with few edges

Cited In (8)

• Counting cliques in 1-planar graphs
• Many cliques with few edges and bounded maximum degree
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• Large cliques and independent sets all over the place
• How many cliques can a clique cover cover?
• Many Cliques in Bounded-Degree Hypergraphs
• Very large cliques are easy to detect
• Exact results on generalized Erdős-Gallai problems

This page was built for publication: Many cliques with few edges

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