|
|||||
|
|
| 连通的K_{n}-残差图 | |
| 引用本文： | 段辉明,李永红. 连通的K_{n}-残差图[J]. 运筹学学报, 2016, 20(2): 38-48. DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.003 |
| 作者姓名： | 段辉明 李永红 |
| 作者单位： | 1. 重庆邮电大学理学院, 重庆 400065 |
| 基金项目： | 国家自然科学基金(No. 61472056), 重庆市自然科学基金(Nos. cstc2015jcyjA00034, cstc 2015jcyjA00015), 重庆市教委科研项目(Nos. KJ15012024, KJ1500403, KJ1400426) |
| 摘 要： | m-K_{n}-残差图是由P. Erd"{o}s, F. Harary和M. Klawe等人提出的, 当m=1时, 他们证明了当nneq1,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}-残差图的最小阶和极图问题. 最后证明了当nneq1,2,3,4时, K_{n+1}timesK_{2}是唯一的具有最小阶的连通的K_{n}-残差图. |
| 关 键 词： | 残差图 最小阶 极图 |
| 收稿时间： | 2015-07-17 |
On connected K_{n}-residual graph |
|
| DUAN Huiming,LI Yonghong. On connected K_{n}-residual graph[J]. OR Transactions, 2016, 20(2): 38-48. DOI: 10.15960/j.cnki.issn.1007-6093.2016.02.003 | |
| Authors: | DUAN Huiming LI Yonghong |
| Affiliation: | 1. College of Science, Chongqing University of Posts and Telecommunications, Chongqing 400065, China |
| Abstract: | The definition of m-K_{n}-residual graph was raised by P. Erd"{o}s, F. Harary and M. Klawe. When nneq 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 nneq 1,2,3,4. |
| Keywords: | residual graph minimum order extremal graph |
| 本文献已被 CNKI 等数据库收录！ | |
| 点击此处可从《运筹学学报》浏览原始摘要信息 | |
| 点击此处可从《运筹学学报》下载全文 | |