连通的三重K_n-残差图

On connected three multiply K_n-residual graphs

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

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 .