4正则无爪图的团横贯数和独立数

来源 :新疆大学 | 被引量 : 0次 | 上传用户:lyzhanhun
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设G=(V,E)是一个简单图,C是G的一个至少有两个顶点的子图,如果C是一个极大的完全子图,则称C是图G的一个团.设D是图G的一个顶点子集,如果对于G的任意一个团C,D∩C?=?,则称D是图G的一个团横贯集.基数最小的团横贯集称为最小团横贯集,最小团横贯集的基数称为最小团横贯数,用τc(G)表示.设I是图G的一个顶点子集,如果对于任意的u,v∈I,uv/∈E,则称I是图G的一个独立集.基数最大的独立集称为最大独立集,最大独立集的基数称为独立数,用α(G)表示.顶点v∈V(G)的开邻集定义为v在G中所有邻点的集合,记为N(v).设H是一个简单图,如果图G中任意顶点的开邻集都同构于H,则称G是H邻域图.例如2K2邻域图每个顶点的开邻集导出的子图都同构于2K2.Wang等2014年已经证明了对于2连通且不含K4的4正则n阶无爪图τc(G)=?n/3?成立,并且猜想所有的不含K4的4正则n阶无爪图的团横贯数τc(G)≤(10n+3)/27.另外,Kang等2013年证明了2连通且不含K4的4正则n阶无爪图的独立数α(G)=?n/3?.进一步,他们也猜想所有的不含K4的4正则n阶无爪图的独立数α(G)≥(8n-3)/27.本文对上述Wang等和Kang等的定理分别给出了简洁的证明,并且解决了上述两个猜想.此外,我们对2K2邻域图G的团横贯数给了一个更好的上界(13n+3)/36,并对P4邻域图和C4邻域图分别给了一个刻画.
其他文献
图的拓扑指标的研究是图论应用研究的一个非常重要的部分.拓扑指标在计算机科学,组合化学,物理及其它应用学科中都有着十分广泛的应用.有关图的各种拓扑指标的研究已有多年的
图谱理论是图论中一个比较热门的研究领域.图谱理论主要研究图的与邻接矩阵,Laplacian矩阵和无符号Laplacian矩阵的特征多项式,特征值和特征向量等有关的属性,以及这些属性与
随着统计学研究与应用范围的不断扩大,具有空间位置信息与时间属性的时空数据得到了很多研究者的重视。在时空数据的分析中最主要的研究是回归关系的时空相关性与时空非平稳
分布鲁棒优化问题(Distributionally Robust Optimization Problems)是建立在考虑最坏情况下进行优化的所谓鲁棒优化问题(Robust Optimization Problems)的基础上,统筹考虑投
红新星由于其特殊的光谱和光度特性一直备受关注。V1309 Sco和V838 Mon的观测数据表明这类恒星很可能是由双星合并产生的。如果是这样,那么红新星的研究就给我们认识双星的合
本文主要采用广义多项式混沌方法求解带有随机输入的热传导方程和带有随机输入的Allen-Cahn方程,通过多项式混沌方法对随机参数空间的处理,一个带有随机输入的偏微分方程就转
除了交易者信念的异质性,与传统金融模型不同的是,两类投资者的风险态度因心理因素而随时间变化,例如前景理论的反射性影响,即:在收益(亏损)情形下风险厌恶(风险偏好)的逆转
在本毕业论文中我们要讨论两个问题。首先,我们构造了D4型量子包络代数Uq(D4)正部分U+q(D4)的极小投射分解的前三步。设k是一个域,A是一个结合的增广(augmented)代数。我们考
一个顶点子集F被称作是一个连通k-子图覆盖(记作V CCk)如果任意k个点的连通子图至少有一个顶点在集合F中.最小赋权的连通k-子图覆盖问题(记作MWV CCk)是指找一个权和最小的顶
Hardy空间的实变理论是调和分析研究的核心内容之一,在分析学领域和偏微分方程中都有重要的应用.设A是Rn上的一个扩张矩阵,φ:Rn×[0,∞)→[0,∞)是一个Musielak-Orlicz函数.