可图序列与m-树

发布时间：2017-11-07 14:10

  本文关键词：可图序列与m-树

  更多相关文章： m-树 度序列 可图序列 实现

【摘要】：图G是m-树,当且仅当G是一个m+1阶完全图,或者G中存在一个度为m的顶点v,使得与v相邻的m个点构成一个团,且G—v是m-树。易见,1树就是通常的树。如果一个图G包含所有k个顶点的m-树作为子图,则称G具有性质Pkm。如果一个非增的非负整数序列π=(d1,…,dn)是某个n阶简单图G的度序列,则称π是一个可图序列,而且G是π的一个实现。如果可图序列π有一个实现具有性质Pkm,则称π是蕴含Pkm-可图的。一个关于蕴含Pkm-可图序列的极值问题考虑如下：确定最小的正整数p,使得对于每一个可图序列π=(d1,…,dn),当n∑di＞p时,π是蕴含Pkm-可图的。这个p记为σ(Pkm,n)。这一问题是属于Erdos等人与-1Goul等人所提出的关于极值图论中的经典Turan数在图的度序列中的变形的新领域。对于m=1,Yin和Li(Acta Mathematica Sinica,English Series,25(2009)795-802)证明,当k≥2且n≥9/2k2+19/2k时,σ(Pk1,n)=(k-2)n。这也是Erdos和So猜想的一个变形。在本论文中,我们主要研究了m=2的情形。本论文的主要结论如下： 1.给出了m-树的一个刻画。 2.证明了当k≥3且其中k≡i(mod3)。
【学位授予单位】：海南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【参考文献】

中国期刊全文数据库 前1条

1 ;A Variation of a Conjecture Due to Erd銉s and Sós[J];Acta Mathematica Sinica(English Series);2009年05期

，

本文编号：1152736