图中特定长度的圈问题

来源 :山东大学 | 被引量 : 0次 | 上传用户:ldbeight
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文介绍图中一定条件的独立的圈及其在一些特殊图中的相关结果。  令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为偶数。
其他文献
1917年,A.K.Erlang提出了有关通信业务的拥塞理论,用统计的方法分析了通信业务量问题,形成了概率论的一个新分支。当人们要使用电话时,如果电话交换机的中断线均已被占用,用
现代数学中,积分方程构成了其重要组成部分,很多学科,像微分方程、计算数学、随机分析、近代泛函分析都与之有紧密联系。由于延迟积分方程数学物理的双向联系,在数学分支中迅
基于非同分布抽样的回归学习算法是核回归学习的一个重要分支。国际著名学习理论专家S.Smale和D.X.Zhou针对非同分布抽样提出边缘分布收敛假设(MDCA),但由于抽样的边缘分布与
KdV-Burgers方程具有广泛的物理背景,不仅大量用于流体力学和气体动力学的研究,而且还可以用来解释如激光波和水波等其他物理现象.KdV-Burgers方程的数值求解方法一直是计算数
L-函数是数论中神秘而特别常见的研究对象,最简单的例子就是Riemannζ函数.类似于Riemannζ函数,一般的L-函数也存在与之相关的广义Riemann假设、广义Ramanujan猜想等问题.众所