连通的三重Kn-残差图

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

On connected three multiply Kn-residual graphs

Erdos P, Harary F and Klawe M studied Kn-residual graphs, and came up with some conclusions and assumptions on m-Kn-residual graphs. In this paper, with the method of including excluding principle and set operations, we studied 3-Kn-residual graphs and got the formula for calculating the minimum order of 3-Kn-residual graphs and constructed its extremal graph when the minimum degree is n. When n = 2, the minimum order of 3-Kn-residual graph is 11, and related extremal graph is constructed. When n = 3, the minimum order is 20, and two non-isomorphic 3-Kn-residual graphs are obtained, which doesn＇t meet the conclusions drawn by ErdSs, et al. When n = 4, the minimum order of 3-K4-residual graph is 22, and related extremal graph is constructed. Besides when n = 8, two non-isomorphic 3-Ks-residual graphs are obtained, and they don＇t meet the conclusions drawn by Erdos, et al. At last, when n = 9, 10, the only extremal graph with minimum order of 48 and 52 respectively validates the conclusions by Erdos, et al .