本文關(guān)鍵詞：4正則無爪圖的團(tuán)橫貫數(shù)和獨(dú)立數(shù)

  更多相關(guān)文章： 團(tuán) 團(tuán)橫貫數(shù) 獨(dú)立數(shù) 無爪圖 4正則圖

【摘要】：設(shè)G=(V,E)是一個簡單圖,C是G的一個至少有兩個頂點(diǎn)的子圖,如果C是一個極大的完全子圖,則稱C是圖G的一個團(tuán).設(shè)D是圖G的一個頂點(diǎn)子集,如果對于G的任意一個團(tuán)C,D∩C?=?,則稱D是圖G的一個團(tuán)橫貫集.基數(shù)最小的團(tuán)橫貫集稱為最小團(tuán)橫貫集,最小團(tuán)橫貫集的基數(shù)稱為最小團(tuán)橫貫數(shù),用τc(G)表示.設(shè)I是圖G的一個頂點(diǎn)子集,如果對于任意的u,v∈I,uv/∈E,則稱I是圖G的一個獨(dú)立集.基數(shù)最大的獨(dú)立集稱為最大獨(dú)立集,最大獨(dú)立集的基數(shù)稱為獨(dú)立數(shù),用α(G)表示.頂點(diǎn)v∈V(G)的開鄰集定義為v在G中所有鄰點(diǎn)的集合,記為N(v).設(shè)H是一個簡單圖,如果圖G中任意頂點(diǎn)的開鄰集都同構(gòu)于H,則稱G是H鄰域圖.例如2K2鄰域圖每個頂點(diǎn)的開鄰集導(dǎo)出的子圖都同構(gòu)于2K2.Wang等2014年已經(jīng)證明了對于2連通且不含K4的4正則n階無爪圖τc(G)=?n/3?成立,并且猜想所有的不含K4的4正則n階無爪圖的團(tuán)橫貫數(shù)τc(G)≤(10n+3)/27.另外,Kang等2013年證明了2連通且不含K4的4正則n階無爪圖的獨(dú)立數(shù)α(G)=?n/3?.進(jìn)一步,他們也猜想所有的不含K4的4正則n階無爪圖的獨(dú)立數(shù)α(G)≥(8n-3)/27.本文對上述Wang等和Kang等的定理分別給出了簡潔的證明,并且解決了上述兩個猜想.此外,我們對2K2鄰域圖G的團(tuán)橫貫數(shù)給了一個更好的上界(13n+3)/36,并對P4鄰域圖和C4鄰域圖分別給了一個刻畫.
【關(guān)鍵詞】：團(tuán) 團(tuán)橫貫數(shù) 獨(dú)立數(shù) 無爪圖 4正則圖
【學(xué)位授予單位】：新疆大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要2-3
• Abstract3-5
• 第一章 引言5-9
• 1.1 基本概念5-6
• 1.2 問題綜述6-9
• 第二章 4正則無爪圖上的團(tuán)橫貫數(shù)和獨(dú)立數(shù)9-14
• 2.1 預(yù)備知識9
• 2.2 4正則無爪圖上的團(tuán)橫貫數(shù)9-13
• 2.3 4正則無爪圖上的獨(dú)立數(shù)13-14
• 第三章 領(lǐng)域圖的簡單刻畫14-17
• 參考文獻(xiàn)17-20
• 碩士期間發(fā)表論文清單20-21
• 致謝21-22

【共引文獻(xiàn)】

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

1 楊大慶;線圖的r-覆蓋[J];福州大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年02期

2 ;The Existence of Even Regular Factors of Regular Graphs on the Number of Cut Edges[J];Acta Mathematica Sinica(English Series);2010年12期

3 Ding Guo WANG;Er Fang SHAN;Zuo Song LIANG;;On the Clique-Transversal Number in(Claw,K_4 )-Free 4-Regular Graphs[J];Acta Mathematica Sinica(English Series);2014年03期

4 Hong Liang LU;Wei WANG;Yuqing LIN;;On Edge Connectivity and Parity Factor[J];Acta Mathematica Sinica;2015年05期

5 ;Minimal regular 2-graphs and applications[J];Science in China(Series A:Mathematics);2006年02期

6 范紅兵;劉桂真;劉季平;;極小正則2-圖及其應(yīng)用[J];中國科學(xué)(A輯:數(shù)學(xué));2005年11期

7 杜彩鳳;;立方圖中的路因子和圈因子[J];科學(xué)技術(shù)與工程;2010年27期

8 南小康;;3-正則圖的1-因子與割邊數(shù)[J];蘭州大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年S1期

9 馬京成;馬登舉;朱s，

本文編號：1052725