论文部分内容阅读
本文介绍图中一定条件的独立的圈及其在一些特殊图中的相关结果。 令G是一个图, V(G)和E(G)分别表示它的顶点集和边集。设v∈V(G),点v在G中的度数用d(v,G)表示,其中图G的最大度和最小度分别用△(G)和δ(G)表示。定义σ2(G)=min{d(x)+d(y)|x,y∈V(G),xy(∈)E(G)}。如果图G中一条路(或一个圈)包含图G的所有点,则称这条路(或这个圈)为G的哈密顿路(或哈密顿圈)。图中独立的圈问题是著名的哈密尔顿圈理论的广义推广。在1952年,Dirac证明了定理:设G是一个顶点数为n≥3的图,若δ(G)≥n/2,则G中有一个哈密顿圈。在1963年,Corrádi和Hajnal证明了如果G是一个顶点数为n≥3k的图并且最小度δ(G)≥2k,则G包含k个独立的圈。2004年,Wang证明了:G是一个顶点数为n的图,满足4k+1≤n≤4k+4,其中k是一个正整数。并且δ(G)≥2k+1,则G含有k个独立的4-圈。本文对图中特定长度的圈问题进行了研究,证明了如下结果: 结果1:设G是一个顶点数为n的图,满足4k+1≤n≤4k+4,其中k为一个正整数。假设σ2(G)≥n。那么G含有k个独立的4-圈。 结果2:令G是一个顶点数为n>4k的图,其中k是一个正整数。假设σ2(G)≥n+1。则G有一个包含k个独立的圈的2-因子,使得其中k-1个是4-圈。 随机图的圈问题得到了许多专家学者的关注。令G(n,p)表示随机图:有n个顶点,边存在的概率为p。2012年,Lee和Sudakov证明了随机图的哈密顿性,如下结论:如果p(》)ln n/n,则G(n,p)中任意最小度至少为(1/2+o(1))np的子图几乎肯定是哈密尔顿的。Shang在2016年,证明了对任意的ε>0,存在常数C=C(ε)满足p≥Cln n/n,则G(n,n,p)的任意最小度至少为(1/2+ε)np的子图几乎肯定是哈密顿的。本文考虑了随图k-部图的哈密顿性,证明以下结论: 结果3:对任意的ε>0,存在常数C=C(ε)满足p≥Cln n/n,则G(n,…,n,p)的任意最小度至少为δ(G)的子图几乎肯定是哈密顿的,其中δ(G)如下:δ(G)>{(k/2-1/k+1+ε)np k为奇数,(k/2-2/k+1+ε)np k为偶数。