独立集可削去的因子临界图的度条件

来源 :华南师范大学 | 被引量 : 0次 | 上传用户:zuhai
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文所涉及的图均为无向,有限,简单图.对边集M(∈)E(G),如果G的任意顶点至多与M中的一条边关联,则称M是G的匹配.称覆盖所有顶点的匹配为完美匹配.称图G是因子临界的,如果对G中任意的顶点u,G-u有一个完美匹配.称图G是独立集可削去因子临界的,如果对于G中任意与|V(G)|有相同奇偶性的独立集I,G-I有完美匹配.在匹配理论中,因子临界图是一类非常重要的图.因为由Gallai-Edmonds分解定理可知,研究图的最大匹配问题只需考虑有完美匹配的图,具有正赢量的图,因子临界图这三类图.当顶点数为奇数时,独立集可削去的因子临界图是一类特殊的因子临界图;当顶点数为偶数时,独立集可削去的因子临界图必然有完美匹配.因此,独立集可削去因子临界图的研究有重要意义.本文研究了独立集可削去的因子临界图的度条件,主要结果如下: 1.一般的独立集可削去的因子临界图的度条件定理2.2设G是一个有n个顶点的图,n≥3.如果对于G中任意不相邻的顶点u和v,有d(u)+d(v)≥2[2n-1/3]-1,那么G是独立集可削去的因子临界图,并且这是最好可能的. 推论2.3设G是一个有n个顶点的图,如果δ(G)≥[2n-1/3],那么G是独立集可削去的因子临界图. 2.无爪的独立集可削去的因子临界图的度条件图G称为无爪图,如果它不包含K1,3作为它的导出子图.引理3.1如果X是无爪图G的一个独立集,那么对任意的u∈V(G-X),|N(u)∩X|≤2. 定理3.3设G是一个有n个顶点的无爪图.如果对于G中任意不相邻的顶点u和v,我们有d(u)+d(v)≥2[n/2]+1,那么G是独立集可削去的因子临界图,并且这是最好可能的. 推论3.4设G是一个有n个顶点的无爪图.如果当n=4m时,δ≥[n/2]+1;否则,δ≥[n/2],那么G是独立集可削去的因子临界图. 定理3.5一个有n个顶点的[n/2]-正则无爪图是独立集可削去因子临界的.(n≠4,9) 定理3.6如果k和n是满足1≤[n/2]≤k≤n-1的正整数,那么任意的有n个顶点的k-正则无爪图G是独立集可削去因子临界的.
其他文献
本文研究了资产清算价格服从一般分布的风险中性内部交易模型。首先,考虑了资产清算价格服从椭圆分布的线性策略型风险中性内部交易模型。在资产清算价格与噪声交易量都具有有
本文通过对荣华二采区10
一、职业教育物理教学中培养创新精神的实在意义长期以来,传统的教育主要采用“讲解加联系”的教学模式。它强调的是基础知识的积累与落实,却忽视了学生对生活的体验与实践,
请下载后查看,本文暂不支持在线获取查看简介。
期刊
同伦论的本质是利用比同胚关系更广泛的等价关系—同伦关系来对拓扑空间进行研究,这也是代数拓扑研究中一种自然的考虑,因为传统的代数不变量(基本群、同调群等)不仅在同胚的空
本文寻求并研究了能够有效求解大规模优化问题的梯度型方法. 第一章综述了梯度型方法的发展历史和现状,其中着重介绍引领梯度法热潮的Barzilai-Borwein(BB)方法。 第二章
本文通过对荣华二采区10
房地产行业是我国国民经济的支柱型行业,由于其广泛纵深的产业链结构,它的发展能直接推动钢铁、建材、银行金融、交通运输等诸多行业的发展,对国民经济的拉动作用十分重大。  
能量控制条件(dominantenergycondition)是正质量定理(PositiveMassTheorem)中一个非常重要的条件。本文研究了在某些假设下,能量控制条件被取代的可能性。在这些假设下,存在一
明218A是三明市农科院以优质常规稻E优540为母本与保持系金23B进行杂交,再与粤丰A测交并连续回交转育而成的野败籼型三系不育系。该不育系具有育性稳定、穗大粒多、开花习性