English

运筹学学报 ›› 2014, Vol. 18 ›› Issue (2): 59-68.

• 运筹学 • 上一篇    下一篇

连通的三重K_{n}-残差图

段辉明1,*, 曾波2, 窦智1   

  1. 1. 重庆邮电大学理学院, 重庆 400065, 2. 重庆工商大学 商务策划学院, 重庆 400067
  • 出版日期:2014-06-15 发布日期:2014-06-15
  • 通讯作者: 段辉明 E-mail:huimingduan@163.com
  • 基金资助:

    国家自然科学基金(No. 71271226), 重庆市教委科学技术研究项目(No. KJ120520)

On connected three multiply K_{n}-residual graphs

DUAN Huiming1,*, ZENG Bo2, DOU Zhi1   

  1. 1. College of Science, Chongqing University of Posts and Telecommunications, Chongqing 400065, China, 2. School of Business Planning, Chongqing Technology and Business University, Chongqing 400067, China
  • Online:2014-06-15 Published:2014-06-15

PDF

626

摘要： Erd\"{o}s P, Harary F和Klawe M研究了K_{n}-残差图, 并对连通的m-K_{n}-残差图提出了一些结论和猜想. 利用容斥原理以及集合的运算性质等方法, 研究了连通的3-K_{n}-残差图, 得到当顶点最小度为n时, 3-K_{n}-残差图最小阶的计算公式以及相应的唯一极图. 当n=2时, 得到最小阶为11以及相应的极图; 当n=3时, 得到最小阶为20并找到两个不同构的极图, 不满足Erd\"{o}s等提出的结论; 当$=4时, 得到最小阶为22及相应的极图; 当n=8, 可以找到两个不同构的3-K_{8_{}}-残差图, 不满足Erd\"{o}s等提出的结论; 最后证明了当n=9,10时, 最小阶分别为48和52以及相应的唯一极图, 验证了  Erd\"{o}s等在文献~(Residually-complete graphs [J]. Annals of Discrete Mathematics, 1980,  6: 117-123) 中提出的结论.

关键词: 残差图, 最小阶, 同构

Abstract: Erd\"{o}s P, Harary F and Klawe M studied $K_{n}$-residual graphs, and came up with some conclusions and assumptions on $m$-$K_{n}$-residual graphs. In this paper, with the method of including excluding principle and set operations, we studied 3-$K_{n}$-residual graphs and got the formula for calculating the minimum order of 3-$K_{n}$-residual graphs and constructed its extremal graph when the minimum degree is $n$. When $n=2$, the minimum order of 3-$K_{2}$-residual graph is 11, and related extremal graph is constructed. When $n=3$, the minimum order is 20, and two non-isomorphic 3-$K_{3}$-residual graphs are obtained, which doesn't meet the conclusions drawn by Erd\"{o}s, et al. When $n=4$, the minimum order of 3-$K_{4}$-residual graph is 22, and related extremal graph is constructed. Besides when $n=8$, two non-isomorphic 3-$K_{8}$-residual graphs are obtained, and they don't meet the conclusions drawn by Erd\"{o}s, et al. At last, when $n=9,10$, the only extremal graph with minimum order of 48 and 52 respectively validates the conclusions by Erd\"{o}s, et al.

Key words: residually graph, minimum order, isomorphic

中图分类号: