关于Erds-Jacobson-Lehel问题的门槛(英文)  

On the Threshold in the Erds-Jacobson-Lehel Problem

作　　者：尹建华[1] 李炯生[1] 

机构地区：[1]中国科学技术大学数学系,安徽合肥230026

出　　处：《应用数学》2002年第1期123-128,共6页Mathematica Applicata

基　　金：ProjectsupportedbytheNationalNaturalScienceFoundationofChina(199710 86)

摘　　要：设σ(k ,n)表示最小的正整数m ,使得对于每个n项正可图序列 ,当其项和至少为m时 ,有一个实现含k+ 1个顶点的团作为其子图 .Erd s等人猜想 :σ(k ,n) =(k - 1 ) ( 2n-k)+ 2 .Li等人证明了这个猜想对于k≥ 5,n≥ k2 + 3是对的 ,并且提出如下问题 :确定最小的整数N(k) ,使得这个猜想对于n≥N(k)成立 .他们同时指出 :当k≥ 5时 ,5k- 12 ≤N(k)≤ k2 + 3.Mubayi猜想 :当k≥ 5时 ,N(k) =5k - 12 .在本文中 ,我们证明了N( 8) =2 0 ,即Mubayi猜想对于kLet σ(k,n) denote the smallest even in teger such that each n-term positive graphic sequence with term sum at leas t σ(k,n) can be realized by a simple graph on n vertices containing a c lique of k+1 vertices. Erds et al. conjectured that σ(k,n)=(k-1)(2n-k )+ 2. Li et al. proved that the conjecture is true for k≥5 and n≥ 2+3, and raised the problem of determining the smallest integer N(k) such that the conjecture holds for n≥N(k) and pointed out that (5k-12

关 键 词：图 度序列 蕴含Ak-可图序列 Erdoes-Jacobson-Lehel问题 Mubayi猜想 

分 类 号：O157.5[理学—数学]