图的控制中的若干结果

来源 :北京理工大学 | 被引量 : 0次 | 上传用户:mmyxj
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设G=(V,E)是一个n阶简单图,S是V的子集,如V-S中的任意点都与S中点相邻,则称S为G的控制集.设S是G的控制集,如S在G中的导出于图G[S]无孤立点,则称S为G的全控制集.如G[S]有完美匹配,则称S为G的对控制集.如G[S]无圈,则称S为G的无圈控制集.G的最小控制集中的点数称为G的控制数γ(G).该文得到了以下主要结论:(1)证明了当G是4-正则图时,γ(G)≤4n/11,从而部分解决了Haynes,Hedetniemi和Slater提出的猜想.(2)证明了当δ(G)≥3时,γ<,t>(G)≤n/2,而且这个界是最好的,从而证明了Favaron等人提出的猜想.(3)证明了当G是3正则图时,γ<,P>(G)≤3n/5,而且这个界是最好的.(4)证明了对于任何正整数K,存在一个直径为2的图G使得γ<,α>(G)-δ(G)≥k,从而解决了Hedetniemi等人提出的一个公开问题.(s)证明了当Δ(G)≥2时,IR(G)-α(G)≤(Δ-2)/(2Δ)n.并且这个界是最好的,从而解决了Rautenbach提出的猜想.(6)证明了存在连通度k(G)=1的图G使得b(G)>Δ(G)+K(G)-1,从而解决了Dunbar等人提出的猜想.(7)证明了如果G是一个顶点数为n的二分图,那么γ<->(G)≥4(√(n+1)-1)-n,从而解决了Dunbar等人提出的猜想.(8)证明了对于任何负整数k和正整数m≥3,存在一个围长为m的图并且γ<->(G)≤k,从而解决了Dumbar等人提出的公开问题.(9)证明了对于任何连通图G,VNI(G)≤[n/3],从而证明了 Gambreill提出的猜想.
其他文献
该文利用Mawhin重合度理论和Krasnoselskii不动点定理,研究泛函微分方程和差分方程解的存在性问题.第一章是绪论,概述了研究背景和主要内容.第二章第二节研究一类迭代微分方
该文讨论几类非线性耗散系统.针对每一个系统,首先证明系统在给定的Sobolev空间中存在吸引子,然后估计吸引子的Hausdorff维数.尽管讨论吸引子的步骤基本相同,但由于讨论的方
针对核孔膜显微图像自动识别的具体问题,本文创新地提出线性并行区域标记方法、对象尺寸统计峰值方法和特征点匹配识别方法。基于上述方法,研制和开发出一套快速、有效的核孔膜
该文主要关心在样本量较小情形下,对于不同的实际问题,如何利用小样本理论对参数和有关量进行统计推断.应用鞍点展开和Laplace方法计算了链长分布及其均值和标准差,并与其他
小学语文教学对于学生的素质发展而言是至关重要的,主要因为语文教学是小学生其他科目学习的基础,也是小学生人际交往的工具,因此,在小学语文教学过程中,教师必须要全面重视
该文研究上下底为流形的三维薄区域Ω上的NS方程的渐近展开问题.我们引入张量分析的工具,采用S-族坐标系来进行研究.我们先研究流形上的NS方程的表现形式以及相应的正则形结
该文选中并讨论了适用于在多种基础网络、平台和设备上的进行远程数据传输和同步的通用同步协议标准SyncML,该标准在2000年12月才由SyncML创始协会制订出来并正式发布,它解决
该论文的主要研究工作共包括两个部分. 第一部分是关于Bernstein型三角插值多项式的线性组合问题的研究.在这里,构造了一个三角插值多项式的Bernstein型的线性组合算子H(f;x,
该论文主要研究了在分形市场假设下如何计算VaR的值.利用VaR理论对中国股票市场进行了实证分析,并就实际数据的计算结果提出了自己的看法,指出了模型中存在的缺陷及今后可能
在中职学校中,《创意设计》课程对于网站建设专业的学生来说是一门非常重要的课程.它不仅要求学生要熟练掌握相关的软件和美术知识,还要求学生拥有一定的想象力和创造力.在教