圖中特定長度的圈問題.pdf

1、本文介紹圖中一定條件的獨立的圈及其在一些特殊圖中的相關結果。
　　令G是一個圖， V(G)和E(G)分別表示它的頂點集和邊集。設v∈V(G)，點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的哈密頓路（或哈密頓圈）。圖中獨立的圈問題是著

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

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

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