运筹学学报 >
2016 , Vol. 20 >Issue 2: 38 - 48
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.02.003
连通的K_{n}-残差图
收稿日期: 2015-07-17
网络出版日期: 2016-06-15
基金资助
国家自然科学基金(No. 61472056), 重庆市自然科学基金(Nos. cstc2015jcyjA00034, cstc 2015jcyjA00015), 重庆市教委科研项目(Nos. KJ15012024, KJ1500403, KJ1400426)
On connected K_{n}-residual graph
Received date: 2015-07-17
Online published: 2016-06-15
m-K_{n}-残差图是由P. Erd\"{o}s, F. Harary和M. Klawe等人提出的, 当m=1时, 他们证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}- 残差图. 首先得到了m-K_{n}-残差图的重要性质, 同时证明了当n=1,2,3,4时, 连通K_{n}-残差图的最小阶和极图, 其中当n=1,2时得到唯一极图; 当n=3,4时, 证明了恰有两个不同构的极图, 从而彻底解决连通的K_{n}-残差图的最小阶和极图问题. 最后证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}-残差图.
段辉明, 李永红 . 连通的K_{n}-残差图[J]. 运筹学学报, 2016 , 20(2) : 38 -48 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.003
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
/
| 〈 |
|
〉 |