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

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.

Cite this article

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

References

[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.
Outlines

/