图的完全子图个数问题

汪小立; 雷澜

doi:10.16357/j.cnki.issn1000-5862.2025.05.15

江西师范大学学报（自然科学版） ›› 2025, Vol. 49 ›› Issue (5) : 539 -544. DOI: 10.16357/j.cnki.issn1000-5862.2025.05.15

图的完全子图个数问题

汪小立, 雷澜

作者信息 +

Author information +

文章历史 +

PDF

摘要

该文用分析的方法探讨在简单连通图G中无（m+1）-完全子图时m-完全子图个数的最大值．先给出当图G中不含3-完全子图时2-完全子图个数的最大值的Mantel定理的一种证明方法;然后，在此基础上获得当图G中不含4-完全子图时3-完全子图个数的最大值;最后，利用数学归纳法得出在n阶简单连通图G中无（m+1）-完全子图时m-完全子图的个数最多有k^m-r（k+1）^r个的一般结论，其中n、m、k、r均为非负整数且n=mk+r（0≤r