Select
On connected three multiply K_{n}-residual graphs
DUAN Huiming, ZENG Bo, DOU Zhi
Operations Research Transactions
2014, 18 (2 ):
59-68.
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.
Reference |
Related Articles |
Metrics |
Comments （0 ）
