连通的三重K_{n}-残差图

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

On connected three multiply K_{n}-residual graphs

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