圖中特定長(zhǎng)度的圈問(wèn)題.pdf

1、本文介紹圖中一定條件的獨(dú)立的圈及其在一些特殊圖中的相關(guān)結(jié)果。
　　令G是一個(gè)圖， V(G)和E(G)分別表示它的頂點(diǎn)集和邊集。設(shè)v∈V(G)，點(diǎn)v在G中的度數(shù)用d(v，G)表示，其中圖G的最大度和最小度分別用△(G)和δ(G)表示。定義σ2(G)=min{d(x)+d(y)|x，y∈V(G)，xy(∈)E(G)}。如果圖G中一條路（或一個(gè)圈）包含圖G的所有點(diǎn)，則稱這條路（或這個(gè)圈）為G的哈密頓路（或哈密頓圈）。圖中獨(dú)立的圈問(wèn)題是著

2、名的哈密爾頓圈理論的廣義推廣。在1952年，Dirac證明了定理:設(shè)G是一個(gè)頂點(diǎn)數(shù)為n≥3的圖，若δ(G)≥n/2，則G中有一個(gè)哈密頓圈。在1963年，Corrádi和Hajnal證明了如果G是一個(gè)頂點(diǎn)數(shù)為n≥3k的圖并且最小度δ(G)≥2k，則G包含k個(gè)獨(dú)立的圈。2004年，Wang證明了:G是一個(gè)頂點(diǎn)數(shù)為n的圖，滿足4k+1≤n≤4k+4，其中k是一個(gè)正整數(shù)。并且δ(G)≥2k+1，則G含有k個(gè)獨(dú)立的4-圈。本文對(duì)圖中特定長(zhǎng)度的圈問(wèn)

3、題進(jìn)行了研究，證明了如下結(jié)果:
　　結(jié)果1:設(shè)G是一個(gè)頂點(diǎn)數(shù)為n的圖，滿足4k+1≤n≤4k+4，其中k為一個(gè)正整數(shù)。假設(shè)σ2(G)≥n。那么G含有k個(gè)獨(dú)立的4-圈。
　　結(jié)果2:令G是一個(gè)頂點(diǎn)數(shù)為n＞4k的圖，其中k是一個(gè)正整數(shù)。假設(shè)σ2(G)≥n+1。則G有一個(gè)包含k個(gè)獨(dú)立的圈的2-因子，使得其中k-1個(gè)是4-圈。
　　隨機(jī)圖的圈問(wèn)題得到了許多專家學(xué)者的關(guān)注。令G(n，p)表示隨機(jī)圖:有n個(gè)頂點(diǎn)，邊存在的概率為p。

4、2012年，Lee和Sudakov證明了隨機(jī)圖的哈密頓性，如下結(jié)論:如果p(》)ln n/n，則G(n，p)中任意最小度至少為(1/2+o(1))np的子圖幾乎肯定是哈密爾頓的。Shang在2016年，證明了對(duì)任意的ε＞0，存在常數(shù)C=C(ε)滿足p≥Cln n/n，則G（n，n，p）的任意最小度至少為(1/2+ε)np的子圖幾乎肯定是哈密頓的。本文考慮了隨圖k-部圖的哈密頓性，證明以下結(jié)論:
　　結(jié)果3:對(duì)任意的ε＞0，存在常數(shù)