图的度序列


摘  要

       Gould，Jacobson 和Lehel（Combinatorics, Graph Theory and Algorithms Vol.1 (1999) ,451-460）考虑了下述经典Turán型极值问题在图的度序列中的变形：对于给定的 图,确定最小的正偶数，使得对于每一个  项可图序列 ，当  时， 有一个实现 包含 作为子图。对于 （ 阶完全图），Erdös，Jacobson 和Lehel证明了：1若  2，则 ；2若n 6，则 。他们同时猜想：对于充分大的 ，有 。近来，Li等人（Discrete Math. 212(2000),Journal of Graph Theory 29(1998),Science in China ,Ser,A,41(1998)）证明了此猜想是成立的。最近， Yin 等人考虑确定经典 Turán数 在图的度序列中的变形值 问题，其中 是一个 完全二部图。2004年，对于充分大的 ，他们确定了 之值。对于 （ 完全三部图），Lai完全确定了 之值, Yin完全确定了 之值。本论文完全确定了 之值。

关键词: 图； 度序列； 蕴含 可图序列

Abstract

       Gould, Jacobson and Lehel (Combinatorics, Graph Theory and Vol.1 (1999), 451-460) considered the following variation of the classical Turán-type extremal problem: for a given graph , determine the smallest positive even integer   such that every   graphic sequence  with term sum  has a realization  containing  as a subgraph. For  (a complete graph on   vertices), Erdös, Jacobson and Lehel proved that   for   2 and  for  . They conjectured that   for sufficiently large  . Li et al. (Discrete Math. 212(2000), Journal of Graph Theory 29(1998), Science in China, Ser, A, 41(1998)) proved that the conjecture is true. Recently, Yin et al. considered the following variation   of the classical Turán-type number  , where  is a   complete bipartite graph. In 2004, they determined   for sufficiently large  . For  （a   complete three-partite graph）, Lai completely determined   and Yin completely determined  . The purpose of this paper is to completely determine  .

Key words: graph; degree sequence; potentially  -graphic sequence


目  录

1引言 1
2一些已知结果 1
3  的下界 3
4 对于 ， 之值 3
5 对于 ， 之值 12
致 谢 13
参考文献 14