数学物理学报 ›› 2009, Vol. 29 ›› Issue (5): 1376-1389.

• 论文 • 上一篇    下一篇

有一个实现包含Kr +1的可图序列

  

  1. 海南大学信息学院数学系 海口 570228
  • 收稿日期:2007-12-28 修回日期:2009-05-30 出版日期:2009-10-25 发布日期:2009-10-25
  • 基金资助:

    国家自然科学基金(10401010, 10861006)、教育部留学回国人员科研启动基金和海南大学2009科研项目(hd09xm87)资助

Graphic Sequences that Have a Realization Containing an K r+1

  1. Department of Mathematics, School of Information Science and Technology, Hainan University, Haikou 570228
  • Received:2007-12-28 Revised:2009-05-30 Online:2009-10-25 Published:2009-10-25
  • Supported by:

    国家自然科学基金(10401010, 10861006)、教育部留学回国人员科研启动基金和海南大学2009科研项目(hd09xm87)资助

摘要:

K r +1是一个r +1个顶点的完全图. 一个可图序列π =(d1, d2, …, dn)称为是蕴含K r+1 -可图的, 如果π有一个实现包含

K r +1作为子图. 该文进一步研究了蕴含K r+1 -可图序列的一些新的条件, 证明了这些条件包含文献[14,10,11]中的一些主要结果和当n ≥ 5r/2 +1时, σ(K r+1, n)之值(此值在文献[2]中被猜测, 在文献[6,7,8,3]中被证实). 此外, 确定了所有满足n ≥ 5, d5 ≥ 4 且不蕴含K5 -可图序列π=(d1, d2, …, dn)的集合.

关键词: 图, 完全图, 度序列

Abstract:

Let K r+1 be the complete graph on r+1 vertices. A graphic sequence π =(d_1,d_2,\cdots ,d_n) is said to be potentially K r+1-graphic if there exists a realization of π containing K r+1 as a subgraph. In this paper, we further investigate a number of new conditions for π to be potentially K r+1-graphic, which imply some previous results in [14,10,11] and the values of σ(K r+1, n) for n ≥ 5r/2 +1, which was conjectured in [2] and was confirmed in [6,7,8,3]. Moreover, we also determine F(4), the set of all graphic sequences π=(d1, d2, …, dn) with n ≥ 5 and d5 ≥ 4 so that π is not potentially K5-graphic.

Key words: Graph, Complete graph, Degree sequence

中图分类号: 

  • 05C07