运筹学学报

• 运筹学 • 上一篇    下一篇

连通的K_{n}-残差图

段辉明1,* 李永红1   

  1. 1. 重庆邮电大学理学院, 重庆 400065
  • 收稿日期:2015-07-17 出版日期:2016-06-15 发布日期:2016-06-15
  • 通讯作者: 段辉明 huimingduan@163.com
  • 基金资助:

    国家自然科学基金(No. 61472056), 重庆市自然科学基金(Nos. cstc2015jcyjA00034, cstc 2015jcyjA00015), 重庆市教委科研项目(Nos. KJ15012024, KJ1500403, KJ1400426)

On connected K_{n}-residual graph

DUAN Huiming1,*  LI Yonghong1   

  1. 1. College of Science, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
  • Received:2015-07-17 Online:2016-06-15 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}-残差图.

关键词: 残差图, 最小阶, 极图

Abstract:

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