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

详细信息    查看全文

• 作者：Jonathan Cutler ; A.J. Radcliffe
• 关键词：Independent sets ; Complete subgraphs ; Extremal enumeration
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：January, 2014
• 年：2014
• 卷：104
• 期：Complete
• 页码：60-71
• 全文大小：242 K

文摘

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 by the Kahn-Zhao theorem . Relaxing the regularity constraint to a minimum degree condition, Galvin conjectured that, for , the number of independent sets in a graph with is at most that in .<p>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 as well. We find it convenient to address this problem from the perspective of . From this perspective, we show that the number of complete subgraphs of a graph G on n vertices with , where with , is bounded above by the number of complete subgraphs in .