连通的三重Kn-残差图

摘要：

Erd(o)s P,Harary F和Klawe M研究了Kn-残差图,并对连通的m-Kn-残差图提出了一些结论和猜想.利用容斥原理以及集合的运算性质等方法,研究了连通的3-Kn-残差图,得到当顶点最小度为n时,3-Kn-残差图最小阶的计算公式以及相应的唯一极图.当n=2时,得到最小阶为11以及相应的极图;当n=3时,得到最小阶为20并找到两个不同构的极图,不满足Erd(o)s等提出的结论;当n=4时,得到最小阶为22及相应的极图;当n=8时,可以找到两个不同构的3-K8-残差图,不满足Erd(o)s等提出的结论;最后证明了当n=9,10时,最小阶分别为48和52以及相应的唯一极图,验证了Erd(o)s等在文献(Residually-complete graphs [J].Annals of Discrete Mathematics,1980,6:117-123)中提出的结论.

关键词：残差图、最小阶、同构

所属期刊栏目：18

分类号：O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金71271226;重庆市教委科学技术研究项目KJ120520

在线出版日期：2014-08-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：59-68