限制条件下图的极大独立集问题

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:njxgfd
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
1960年,Erd(o)s和Moser提出在一般n阶无向图G中求极大独立集个数的最大值,以及何时达到最大值的问题.Erd(o)s解决了这个问题,随后,Moon和Moser也独立的给出了这个问题的相关结果.数十年来,关于各种特殊图类的极大独立集问题得到了广泛的研究.研究限制条件下图的极大独立集的计数问题是关于图的独立集研究的主要方向.   本文在前人的工作基础上,运用数学归纳法和构造反例等方法,继续研究限制条件下图的极大独立集问题,主要结果如下:   (1)在对树的极大独立集的计数研究中,其对应的极图(树)的结构一般只含有一个最大度点.本文我们研究了含有两个最大度点的树的极大独立集个数的最大值,同时刻画取得最大值时的树的结构;   (2)同样的,关于树的极大独立集个数,不管是第一、第二、还是第三最值,大部分极图(树)的直径都比较小.本文给出了直径较大时树的极大独立集个数的最大值,同时刻画取得最大值时的树的结构;   (3)最后本文对单圈图的线图中的极大独立集的计数问题开展研究,刻画了单圈图线图中含有最大极大独立集个数的极图结构特征.
其他文献
期刊
小学时期是学生学习最为关键的基础阶段,对于学生在文学素养方面的培养更是小学教师义不容辞的责任所在。因此,在素质教育和新课标课程不断深入小学课堂中的这种情况,表明我
数字签名技术作为保证信息完整性和身份认证的重要工具,已成为信息安全领域的一个关键技术。环签名作为一种签名者完全匿名技术得到了广泛的应用。量子计算机的出现对传统公
针对农村籍女大学生就业难问题,文章在阐述大学生就业联动机制基本内涵的基础上,论述了以政府、高校、用人单位、家庭和大学生自身等五大主体角色为内容的联动机制实现途径,以帮
文字录入是学生受用终生的一项重要的技能,如同握笔写字一样,是学生提高信息技术素养的一个重要基石.在文字录入学习及应用过程中,涉及家庭、学生兴趣、课程安排等众多因素,
本文以滑轮组机械效率的定义为切入点,对其相关例题做细致的探讨研究,期望为提升初中滑轮组机械效率知识的教学质量,与优化学生的学习效率,提供有益的参考。
文章针对三种主要量子纠错码的多量子比特纯态的纠缠进行了研究.在量子计算和量子信息领域,量子纠缠不仅是一种重要的物理资源而且也是量子理论的最主要特征,已经成为重要的研
期刊
非线性发展方程解的爆破理论是偏微分方程的重要内容。在本文第二章中,我们首先研究了一类带有反平方势函数的半线性热方程:ut=△u-V(x)u+a(x)Up在非局部非线性边界条件:u=∫ΩK
改革开放以来特别是党的十六大以来,我国非公有制经济迅速发展,非公有制经济组织党建工作面临新的形势和挑战。非公有制经济组织党建工作在长期的探索实践中,积累了不少成功