Premium
The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree
Author(s) -
Cutler Jonathan,
Radcliffe A. J.
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22016
Subject(s) - conjecture , mathematics , combinatorics , graph , degree (music) , discrete mathematics , physics , acoustics
In this article, 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 Δ ( G ) ≤ r , which has the most complete subgraphs of size t , for t ≥ 3 . The conjectured extremal graph is a K r + 1 ∪ K b , where n = a ( r + 1 ) + b with 0 ≤ b ≤ r . Gan et al. (Combin Probab Comput 24(3) (2015), 521–527) proved the conjecture when a ≤ 1 , and also reduced the general conjecture to the case t = 3 . We prove the conjecture for r ≤ 6 and also establish a weaker form of the conjecture for all r .