本文關(guān)鍵詞：可圖序列與m-樹

  更多相關(guān)文章： m-樹 度序列 可圖序列 實(shí)現(xiàn)

【摘要】：圖G是m-樹,當(dāng)且僅當(dāng)G是一個m+1階完全圖,或者G中存在一個度為m的頂點(diǎn)v,使得與v相鄰的m個點(diǎn)構(gòu)成一個團(tuán),且G—v是m-樹。易見,1樹就是通常的樹。如果一個圖G包含所有k個頂點(diǎn)的m-樹作為子圖,則稱G具有性質(zhì)Pkm。如果一個非增的非負(fù)整數(shù)序列π=(d1,…,dn)是某個n階簡單圖G的度序列,則稱π是一個可圖序列,而且G是π的一個實(shí)現(xiàn)。如果可圖序列π有一個實(shí)現(xiàn)具有性質(zhì)Pkm,則稱π是蘊(yùn)含Pkm-可圖的。一個關(guān)于蘊(yùn)含Pkm-可圖序列的極值問題考慮如下：確定最小的正整數(shù)p,使得對于每一個可圖序列π=(d1,…,dn),當(dāng)n∑di＞p時,π是蘊(yùn)含Pkm-可圖的。這個p記為σ(Pkm,n)。這一問題是屬于Erdos等人與-1Goul等人所提出的關(guān)于極值圖論中的經(jīng)典Turan數(shù)在圖的度序列中的變形的新領(lǐng)域。對于m=1,Yin和Li(Acta Mathematica Sinica,English Series,25(2009)795-802)證明,當(dāng)k≥2且n≥9/2k2+19/2k時,σ(Pk1,n)=(k-2)n。這也是Erdos和So猜想的一個變形。在本論文中,我們主要研究了m=2的情形。本論文的主要結(jié)論如下： 1.給出了m-樹的一個刻畫。 2.證明了當(dāng)k≥3且其中k≡i(mod3)。
【學(xué)位授予單位】：海南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前1條

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

，

本文編號：1152736