Acta mathematica scientia,Series A ›› 2009, Vol. 29 ›› Issue (5): 1376-1389.

• Articles • Previous Articles     Next Articles

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)资助

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

CLC Number: 

  • 05C07
Trendmd