图中特定长度的圈问题

来源 :山东大学 | 被引量 : 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提出了有关通信业务的拥塞理论,用统计的方法分析了通信业务量问题,形成了概率论的一个新分支。当人们要使用电话时,如果电话交换机的中断线均已被占用,用
“物理是一门以实验为基础的科学”.初中物理课程标准中指出:“教学中应重视观察和实验,使学生通过观察和实验来理解和掌握物理概念、原理及规律”.这些论断的宗旨是通过实验
2017年,江苏省广播电视总台(集团)城市频道实现了传统媒体广告经营困境中的逆势增长。截至9月份,频道广告创收较去年同期增长40%以上,新增投放品牌超过20个,这场漂亮的“突围
现代数学中,积分方程构成了其重要组成部分,很多学科,像微分方程、计算数学、随机分析、近代泛函分析都与之有紧密联系。由于延迟积分方程数学物理的双向联系,在数学分支中迅
基于非同分布抽样的回归学习算法是核回归学习的一个重要分支。国际著名学习理论专家S.Smale和D.X.Zhou针对非同分布抽样提出边缘分布收敛假设(MDCA),但由于抽样的边缘分布与
KdV-Burgers方程具有广泛的物理背景,不仅大量用于流体力学和气体动力学的研究,而且还可以用来解释如激光波和水波等其他物理现象.KdV-Burgers方程的数值求解方法一直是计算数
L-函数是数论中神秘而特别常见的研究对象,最简单的例子就是Riemannζ函数.类似于Riemannζ函数,一般的L-函数也存在与之相关的广义Riemann假设、广义Ramanujan猜想等问题.众所
经常有人用“切蛋糕的刀”来形容分级基金的分级方式,因为如果把基金收益比喻为蛋糕,那么分级方式恰如一把切蛋糕的刀子,将基金收益分割成不同风险收益特征的份额,让投资者根
随着新课改的不断实施,体育游戏在体育教学中成为主要内容.体育作为小学生生活的重要组成部分,对培养学生认识世界和锻炼身体起着重要作用,在小学体育教学中进行有趣的体育游
今天,中国质量协会在京举办首届全国服务质量高层论坛暨首届全国优质服务大赛。我们很荣幸地邀请到来自有关政府部门、有关行业协会和服务业优秀企业的嘉宾、代表共同出席今