图的2-控制数与独立控制数的新的上界

来源 :新疆大学 | 被引量 : 0次 | 上传用户:naicha125
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
令G是一个点集为V(G),边集为E(G)的图.设D是V(G)的一个子集,如果V(G)\D中的每个点在D中至少有k个邻点,就称D是G的一个k-控制集.图G的最小k-控制集的阶数,称为图G的k-控制数,记作γk(G).设S是V(G)的一个子集,如果S中的任意两点在G中都不相邻,就称S是G的一个独立集图G的最大独立集的阶数,称为图G的独立数,记作α(G).如果一个集合I既是G的独立集,又是G的控制集,就称I是G的一个独立控制集.图G的最小独立控制集的阶数,称为G的独立控制数,记作i(G).本文的研究内容主要是围绕以下三个猜想:1.γ2(G)≤n-m(G)+1,其中m(G)是图G的度序列的中位数.2.i(G)≤α(G-L)+2/3Δ(G[L]),其中L是度数大于n/2的点的集合.3.i(G)≤α(G-L),其中L是度数大于n/2的点的集合且是独立集.对于猜想1,我们首先证明了弱一点的结果:γ2(G):≤n-δ(G)+1.其次,在已知二部图对该猜想成立的基础上,我们证明了最小度δ(G):≥2的无三角形图满足γ2(G)≤n-Δ(G),其中Δ(G)表示图G的最大度.我们还拓展了超图的一个性质,进而证明了该猜想对分裂图成立.对于猜想2,猜想3,我们证明了这两个猜想对平面图成立.并且我们证明了猜想3对无三角形图,无爪图和分裂图成立.除此之外,我们给出了猜想3成立的一个充分条件:|L|+m≤4.
其他文献
题画诗是中国古代出现的诗画结合的重要艺术样态,但关于题画诗的起源,目前学界尚未取得统一的认识,据有关学者粗略统计,有近二十种观点。从题画诗的演进来看,唐代以前就已出
企业所产生的巨大碳排放量是造成气候变化的重要因素,各利益相关者要求其按时披露公司的碳排放情况,并对社会影响负责。对于高能源消耗的制造业来说,应积极开展节能减排工作,将环境战略与经济战略相结合,重新考虑自身发展与资源环境的关系。但任何企业的发展至始至终都围绕其经济目标展开,而开展节能减排工作意味着将会分散企业对其核心领域的资源投入和管理工作,在提升企业碳绩效水平的同时会使得企业相关营运成本上升。低碳
隔代教育是由于年轻父母无暇照顾儿童而选择与祖辈共同承担儿童的教育责任或完全托付给祖辈的一种家庭教育模式。隔代教育对隔代教育儿童产生了很大影响,尤其是对儿童行为习惯的影响不容忽视。本文以社会化相关理论为基础,运用社会学相关定量与定性研究方法展开调研,调查以隔代教育儿童为对象,从祖辈的年龄、受教育程度、教育观念、教育方法出发,了解隔代教育对儿童带来的积极影响与消极影响。本文运用问卷调查法、访谈法、文献
YD公司坐落于秦皇岛经济技术开发区,属于国家政策支持的高新技术企业,如何利用现有的技术优势形成公司整体的竞争优势,从而持续获得更大的市场份额,成为本文研究的重点与核心。战略管理的目的是为了企业的未来把握和创造新的机遇,在全球经济激烈竞争的大环境下,在新冠疫情的严重影响下,一个企业要寻求生存与发展,就必须制定出与企业向匹配的发展战略,形成企业独特的核心竞争力,长此以往的保持住竞争优势。YD公司若想在
在现代社会中,随着信息技术的快速发展,人类的工作与生活已经发生了极大的改变。信息技术对教育也产生了巨大的影响。信息化教育要求当代教师成为具备信息技术能力的新型专业
本篇翻译实践报告的翻译材料选自澳大利亚作家安妮·菲利普斯的社会学著作《没有文化的多元文化主义》,其译文约为10000词。该文本主要描述澳大利亚的多元文化主义,其中涉及
目的:比较Ⅱ、Ⅲ期胰腺癌患者接受影像引导下放射性125I粒子植入与传统外科手术治疗的疗效,探讨放射性125I粒子植入与传统外科手术相比在近期疗效、并发症、生存期等方面的差
本次翻译实践的材料以《澳大利亚2025》中社会部分为语料,该文本详述了澳大利亚各个领域的法律法规,中老年人等的相应福利政策,以及建筑风格的类型,设计特点等等。该翻译文本
目的:泌乳素瘤是一种垂体瘤的高发类型,约占全部垂体瘤的40%。垂体瘤的治疗策略包括手术、放疗和药物治疗,其中药物治疗以多巴胺2类受体激动剂为主。术前多巴胺受体激动剂的
目的:本课题旨在通过临床随机对照试验,评估赖氏通元针法治疗气滞血瘀型突发性耳聋的有效性及安全性,初步探讨通元疗法治疗气滞血瘀型突发性耳聋的作用机制,为今后通元针法治疗气滞血瘀型突发性耳聋提供临床依据。方法:选取2018年10月至2019年12月期间于广州中医药大学附属中山市中医院耳鼻喉科气滞血瘀型突发性耳聋住院患者共60例。根据随机对照分组原则,将60例患者随机分为对照组与治疗组,每组各30例。对