运筹学

连通的K_{n}-残差图

展开
  • 1. 重庆邮电大学理学院, 重庆 400065

收稿日期: 2015-07-17

  网络出版日期: 2016-06-15

基金资助

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

On connected K_{n}-residual graph

Expand
  • 1. College of Science, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

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

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.

参考文献

[1] Harary F, Klawe M. Residually-complete graphs [J]. Annals of Discrete Mathematics, 1980, 6: 117-123.
[2] 杨世辉, 段辉明. 奇阶完备残差图 [J]. 应用数学学报, 2011, 34(5): 778-785.
[3] Liao J D, Yang S H, Deng Y. On connected 2-K_{n}-residual graphs [J]. Mediterranean Journal of Mathematics, 2012, 10: 1660-1677.
[4] Liao J D, Yang S H. Two improvement on the Erdos, Harary and Klawe conjecture [J]. Mediterranean Journal of Mathematics, 2014, 6: 2160-2176.
[5] 段辉明, 曾波, 窦智. 连通的三重K_n-残差图 [J]. 运筹学学报, 2014, 18(2): 778-785.
[6] Duan H M, Zeng B, Jin L Y. On connected m-K_2-residual graphs [J]. Ars Combinatoria, 2016, 125(1): 23-32.
[7] Holusa M.  Image segmentation using iterated graph cuts with residual graph [J]. Eduard Sojka in Advances in Visual Computing, 2013, 1: 228-237.
[8] Trotta B. Residual properties of simple graphs [J]. Bulletin of the Australian Mathematical Society, 2010, 82(3): 488-504.
[9] 段辉明, 李永红. 关于m-HPK(n_{1},n_{2},n_{3},n_{4})-残差图 [J]. 数学杂志, 2014, 34(2): 324-334.
[10] Duan H M. On connected m multiply 2 dimensions composite hyperplane complete graphs [J]. Journal of Discrete Mathematical Sciences and Cryptography, 2013, 16(6): 313-328.
文章导航

/