本文關(guān)鍵詞：圖中具有特定條件的點(diǎn)不交的圈

  更多相關(guān)文章： 圖 圈 點(diǎn)不交 二分圖

【摘要】：本文主要介紹圖中具有特定條件的點(diǎn)不交的圈。圖G中含有k個(gè)頂點(diǎn)的路或圈分別記為k-路或k-圈。若一條路(或一個(gè)圈)包含圖G的全部頂點(diǎn),則稱這條路(或這個(gè)圈)為G的Hamilton(哈密爾頓)路(或Hamilton圈)。圖中點(diǎn)不交的圈的問題是著名的Hamilton圈理論的一個(gè)推廣。Catlin (Ph. D.Dissertation.Ohio State University,1976),Aiger,Brandt(J.London Math.Soc,1993,48(2):39-51)和Alon(Discrete Math.,1996,152(1):13-23)分別給出了圖中含點(diǎn)不交的圈的度條件。1984年,El-Zahar給出了下列猜想：設(shè)G是一個(gè)含有n=n1+n2+…+nk(ni≥3,1≤i≤k)個(gè)頂點(diǎn)的簡(jiǎn)單圖,若則G包含κ個(gè)點(diǎn)不交的圈C1,C2,…,Ck,其長(zhǎng)度分別為n1,n2,…,nk.此猜想至今未得到解決。但是El-Zahar在同一篇論文中證明了k=2時(shí)的情況：設(shè)G是一個(gè)含有n=n1+n2個(gè)頂點(diǎn)的簡(jiǎn)單圖,若則G包含兩個(gè)點(diǎn)不交的圈C1,C2,其長(zhǎng)度分別為n1,n2。2009年,Gao,Yan和Li(J.Appl.Math.Comput.2009,31:203-215)給出了二分圖中包含特定點(diǎn)的點(diǎn)不交的圈問題的度條件。本文中證明了如下結(jié)果：結(jié)果1：設(shè)G是一個(gè)含有n個(gè)頂點(diǎn)的簡(jiǎn)單圖,若對(duì)G中任意兩個(gè)不相鄰的點(diǎn)x,y,有d(x)+d(y)≥n+4,則對(duì)任意的(n1,n2),ni≥2,n=n1+n2,G包含兩個(gè)點(diǎn)不交的圈C1,C2,其長(zhǎng)度分別為n1,n2。結(jié)果2：設(shè)k是一個(gè)正整數(shù),G是一個(gè)含有n≥4k個(gè)頂點(diǎn)的簡(jiǎn)單圖。若對(duì)于G中任意一對(duì)不相鄰的點(diǎn)x,y有max{d(x),d(y)}≥2k,則G包含κ點(diǎn)不交的圈。結(jié)果3：令G=(V1,V2,E)是一個(gè)二分圖,|V1|=|V2|=n≥2k+1,其中k≥1是一個(gè)整數(shù)。若對(duì)G中任意兩個(gè)不相鄰的點(diǎn)x∈V1,y∈V2,有d(x)+d(y)≥n+k,則對(duì)G中的任意k個(gè)不同的點(diǎn)v1,v2,…,vk,G都包含k-1個(gè)點(diǎn)不交的4-圈C1,C2,…,Ck-1和一條含有2t個(gè)頂點(diǎn)的路Pk,其中t=n-2(k-1),使得每個(gè)圈和路Pk中都包含一個(gè)特定的點(diǎn)。結(jié)果4：令G=(V1,V2,E)是一個(gè)二分圖,|V1|=|V2|=n≥2k+1,其中k≥1是一個(gè)整數(shù)。若對(duì)G中任意兩個(gè)不相鄰的點(diǎn)x∈V1,y∈V2,有d(x)+d(y)≥n+k,則對(duì)G中的任意k個(gè)不同的點(diǎn)v1,v2,…,vk,G都包含k個(gè)點(diǎn)不交的圈C1,C2,…,Ck,使得每個(gè)圈中都包含一個(gè)特定的點(diǎn),并且這k個(gè)圈中有k-1個(gè)是4-圈。
【關(guān)鍵詞】：圖 圈 點(diǎn)不交 二分圖
【學(xué)位授予單位】：山東大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5
【目錄】：

• 中文摘要6-8
• 英文摘要8-10
• 符號(hào)說(shuō)明10-11
• 第一章 前言11-21
• §1.1 基本概念11-13
• §1.2 圖中的圈理論的發(fā)展13-21
• 第二章 圖中的2-因子21-29
• §2.1 主要結(jié)果21-22
• §2.2 相關(guān)引理22-26
• §2.3 定理2.1.1的證明26-29
• 第三章 圖中點(diǎn)不交的圈29-38
• §3.1 預(yù)備知識(shí)及定理29-30
• §3.2 相關(guān)引理30-33
• §3.3 定理3.1.1的證明33-38
• 第四章 二分圖中點(diǎn)不交的圈38-50
• §4.1 預(yù)備知識(shí)及定理38-40
• §4.2 相關(guān)引理40-43
• §4.3 定理的證明43-50
• 參考文獻(xiàn)50-54
• 致謝54-55
• 已完成和發(fā)表的論文55-56
• 學(xué)位論文評(píng)閱及答辯情況表56

【相似文獻(xiàn)】

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

1 楊宏晨;關(guān)于k-消去二分圖的一些結(jié)果[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2003年11期

2 楊宏晨,薛秀謙;二分圖為k-消去圖的 2個(gè)條件(英文)[J];Journal of Southeast University(English Edition);2003年02期

3 李峰;耿建艷;李碩;梁峰;;一種用4-圈和8-圈對(duì)二分圖的劃分[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2008年06期

4 王宏祥,蘇磊,車文剛;二分圖的無(wú)關(guān)分解[J];云南工業(yè)大學(xué)學(xué)報(bào);1998年01期

5 車軍領(lǐng);關(guān)于二分圖的2-因子[J];山東師大學(xué)報(bào)(自然科學(xué)版);2000年03期

6 錢建波;二分圖中k-因子存在的兩個(gè)充分條件[J];山東大學(xué)學(xué)報(bào)(自然科學(xué)版);2001年04期

7 顏謹(jǐn);二分圖中相互獨(dú)立的圈[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2002年05期

8 石建軍;何大韌;;二分圖的投影、邊權(quán)及點(diǎn)強(qiáng)度[J];商丘師范學(xué)院學(xué)報(bào);2009年09期

9 汪小玲;;滿足某些不等式條件的置換與二分圖[J];西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2010年03期

10 周磊;支蓉;馮愛霞;龔志強(qiáng);;基于二分圖的溫度網(wǎng)絡(luò)拓?fù)湫再|(zhì)研究[J];物理學(xué)報(bào);2010年09期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前2條

1 楊楠;丁暉;劉悅;;Web社區(qū)緊密核的抽取方法[A];NDBC2010第27屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集(B輯)[C];2010年

2 付春花;劉愛芬;陳卓輝;何大韌;;合作-競(jìng)爭(zhēng)網(wǎng)絡(luò)的二分圖描述建議[A];中國(guó)數(shù)學(xué)力學(xué)物理學(xué)高新技術(shù)交叉研究學(xué)會(huì)第十二屆學(xué)術(shù)年會(huì)論文集[C];2008年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 高云澍;圖中存在獨(dú)立圈及指定條件因子的度條件[D];山東大學(xué);2009年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 朱文;基于時(shí)序二分圖的優(yōu)化派工方法研究及Web實(shí)現(xiàn)[D];南京理工大學(xué);2015年

2 張紹華;圖中具有特定條件的點(diǎn)不交的圈[D];山東大學(xué);2016年

3 魯富榮;二分圖的因子[D];山西大學(xué);2007年

4 劉瓊;包含大圈的2-因子在二分圖中的存在性[D];江西師范大學(xué);2007年

5 朱瑯;基于二分圖的查詢推薦算法[D];安徽大學(xué);2014年

6 鄭思遠(yuǎn);基于二分圖的混合推薦系統(tǒng)的研究與實(shí)現(xiàn)[D];北京郵電大學(xué);2015年

7 李改枝;基本極大（m+1）K_2-free二分圖[D];河南大學(xué);2009年

8 蔡瑩瑩;基于二分圖的應(yīng)急預(yù)案體系有效性研究[D];大連理工大學(xué);2012年

9 李金娜;關(guān)于圖的[k，，k+1]-因子的若干結(jié)果[D];東北大學(xué);2006年

10 李峰;圖的獨(dú)立圈和2-因子理論的幾個(gè)最新結(jié)果[D];山東大學(xué);2009年

本文編號(hào)：724964