Operations Research Transactions >
2016 , Vol. 20 >Issue 2: 38 - 48
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.02.003
On connected K_{n}-residual graph
Received date: 2015-07-17
Online published: 2016-06-15
The definition of m-K_{n}-residual graph was raised by P. Erd\"{o}s, F. Harary and M. Klawe. When n\neq 1,2,3,4, they proved that K_{n+1}\times K_{2} is only connected to K_{n}-residual graph which has minimum order. In this paper, we have studied m-K_{n}-residual graph, and obtained some important properties. At the same time, we proved that the connected K_{n}-residual graph of the minimum order and the extremal graph for n=1,2,3,4. When n=1,2, it is the only extremal graph. When n=3,4, we proved just two connected residual graph non isomorphic with the minimum order, so as to thoroughly solve the connected K_{n}-residual graph of the minimum order and extremal graph's problems. Finally we prove that K_{n+1}\times K_{2} is only connected with the minimum order of K_{n}-residual graph, when n\neq 1,2,3,4.
Key words: residual graph; minimum order; extremal graph
DUAN Huiming, LI Yonghong . On connected K_{n}-residual graph[J]. Operations Research Transactions, 2016 , 20(2) : 38 -48 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.003
/
〈 |
|
〉 |