附加二部图条件的Erd(?)s-Sós猜想的若干讨论

来源 :中国科学技术大学 | 被引量 : 0次 | 上传用户:wintry5
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
极图理论中著名的Erd(?)s-Sós猜想指出,对于n阶图G,若其边数大于n(k-2)/2,则所有k阶树都是G的子图。基于树是连通二部图的事实,本文考虑对图G附加二部图条件。在附加二部图条件下,本文证明了如下几类树是图G的子图:(1)直径为5的树;(2)最大度大于等于「k-1/2」的树;(3)二部划分几乎平衡的树;(4)直径大于等于k-4的树。此外,本文证明了在附加二部图条件下,当k≤12时,Erd(?)s-Sós猜想成立。在二部图条件下还有一个有趣的发现:若所有直径为2m的k阶树是G的子图,则所有直径为2m+1的k阶树也是G的子图。这个发现告诉我们在此条件下只须考虑直径为偶数的树即可。相比于Erd(?)s-Sós猜想的已知结果,本文在附加二部图条件下得到了更强的结果。本文所使用的主要方法是图的嵌入,特别是固定某些顶点的嵌入。使用这一方法的动机来源于对图G的观察:如果一个图的平均度大于k-2,那么它包含一个平均度大于k-2的子图,且这个子图的最小度大于等于「k/2」。
其他文献
随着5G网络的兴起以及自动驾驶技术的普及,许多制造商都在争取着将自动驾驶车辆投入市场,这将极大地刺激自动驾驶技术的兴起,而定位技术将是一个关键的基础技术。然而定位技术现阶段还存在着巨大的挑战。一些像GNSS等的定位技术已经逐步的被应用与自动驾驶定位当中,而动态信息共享定位的新技术在自动驾驶定位技术中也逐步得到了重视。本文主要基于后验线性置信传播算法(PLBP)对自动驾驶车辆进行协作定位,该算法分为
甘薯在我国种植历史悠久,种植面积和产量均居世界首位,在国内粮食作物产量排名中位列第四,仅次于水稻、小麦和玉米,不仅可以作为粮食作物,在能源领域和保健功能上也发挥重要
目的:本研究旨在探讨脾弹性是否可以鉴别肝硬化患者轻度和中重度食道胃底静脉曲张,为临床医生的诊疗工作提供帮助。方法:从2017年10月-2019年12月收集诊断为肝硬化的患者,行
马铃薯是世界第四大作物,由卵菌Phytophthora infestans(Mont.)de Bary导致的晚疫病是马铃薯上的毁灭性病害,一直是限制马铃薯生产的一个关键要素。然而晚疫病菌生理小种进化
目的:通过生物信息学分析HOTAIR与hsa-miR-148b-3p是否存在结合,进而通过细胞学实验验证在乳腺癌细胞系中两者互作关系如何,为下一步探究两者调控机制提供方向。方法:本研究
坛紫菜(Pyropia haitanensis)是我国南方沿海广泛栽培的的大型经济海藻,其产量占全国紫菜总产量的75%。近年来由于全球气候变暖的影响,高温烂苗、种质退化等问题严重制约着紫
目的:对疫源地中发热伴血小板减少综合征病毒及斑点热群立克次体的感染情况进行筛查。方法:对辽宁省宽甸县、凤城市及中国医科大学附属第一医院收集的符合本研究纳入标准的患
目的:为了实现联合国90-90-90目标,2016年世界卫生组织(World Health Organization,WHO)建议所有人类免疫缺陷病毒(Human Immunodeficiency Virus,HIV)感染者应尽可能在确诊
禽传染性支气管炎(Avian infectious bronchitis,IB)是禽传染性支气管炎病毒(Avian infectious bronchitis virus,IBV)引起的一种鸡的急性、高度接触性呼吸道传染病。IBV属于
目的:1.总结EBUS-TBNA影像上肺癌纵隔淋巴结转移的超声影像学特征,探讨EBUS-TBNA超声内镜下肺癌纵隔淋巴结转移与纵隔淋巴结良性肿大的鉴别诊断价值,以期提高EBUS-TBNA对肺癌