图中特定长度的圈问题

发布时间：2018-11-14 11:57

【摘要】：本文介绍图中一定条件的独立的圈及其在一些特殊图中的相关结果。令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(?)(G)}。如果图G中一条路(或一个圈)包含图G的所有点,则称这条路(或这个圈)为G的哈密顿路(或哈密顿圈)。图中独立的圈问题是著名的哈密尔顿圈理论的广义推广。在1952年,Dirac证明了定理:设G是一个顶点数为n ≥ 3的图,若δ(≥n/2,则G中有一个哈密顿圈。在1963年,Corradi和Hajnal证明了如果(?是一个顶点数为n ≥ 3κ的图并且最小度δ(G)≥ 2κ,则G包含k个独立的圈。2004年,Wang证明了:G是一个顶点数为n的图,满足4κ + 1≤n≤4k+4,其中κ是一个正整数。并且δ(G)≥2κ + 1,则G含有κ个独立的4-圈。本文对图中特定长度的圈问题进行了研究,证明了如下结果:结果1:设G是一个顶点数为n的图,满足4κ + 1≤n≤4κ:+ 4,其中k为一个正整数。假设σ2(G)≥n。那么G含有k个独立的4-圈。结果2:令G是一个顶点数为n4κ的图,其中κ是一个正整数。假设σ2(G)≥n + 1。则G有一个包含κ个独立的圈的2-因子,使得其中κ-1个是4-圈。随机图的圈问题得到了许多专家学者的关注。令G(n,p)表示随机图:有n个顶点,边存在的概率为p。2012年,Lee和Sudakov证明了随机图的哈密顿性,如下结论:如果p》lnn/n,则G(n,p)中任意最小度至少为(1/2 + o(1))np的子图几乎肯定是哈密尔顿的。Shang在2016年,证明了对任意的ε0,存在常数C = C(ε)满足pCln n/n，/n(则n,p)的任意最小度至少为(1/2 + ε)np的子图几乎肯定是哈密顿的。本文考虑了随图κ-部图的哈密顿性,证明以下结论:结果3:对任意的ε0,存在常数C = C(ε)满足p≥ Cln n/n,则G(n,...,n,p)的任意最小度至少为δ(G)的子图几乎肯定是哈密顿的,其中δ(G)如下:(?)为奇数,为偶数。
[Abstract]:In this paper, we introduce the independent cycles of some conditions in graphs and their related results in some special graphs. Let G be a graph, V (G) and E (G) represent its vertex set and edge set respectively. Let the degree of v 鈭，

本文编号：2331093