【摘 要】
：
设F是图G的[m]-匹配构成的集合,如果满足∪M∈FM=E(G),则称F是图G的一个[m]-覆盖.图G的[m]-覆盖所包含的[m]-匹配的最小个数称为图G的过度[m]-指标,记为χ′[m](G).当[m]-匹
论文部分内容阅读
设F是图G的[m]-匹配构成的集合,如果满足∪M∈FM=E(G),则称F是图G的一个[m]-覆盖.图G的[m]-覆盖所包含的[m]-匹配的最小个数称为图G的过度[m]-指标,记为χ′[m](G).当[m]-匹配为完美匹配或近似完美匹配时,对应的参数称为图G的过度指标,记为χ′e(G).当m取值很小时,对任意的图G,显然有χ′[1](G)=|E(G)|.对[2]-可覆盖的图,有χ′[2](G)=max{χ′(G),|E(G)|/2},其中χ′(G)是图G的边染色数.对[3]-可覆盖的图,Cariolaro和Fu证明了χ′[3](G)=max{χ′(G),|E(G)|/3,s(G)},其中s(G)是图G的分裂数.他们进一步证明了对[3]-可覆盖的树,有χ′[3](T)=max{χ′(T),|E(T)|/3}.Mazzuoccolo证明了对[4]-可覆盖的树,有χ′[4](T)=max{χ′(T),|E(T)|/4,s(T)}.然而随着m的增加,计算任意的m和任意图G的过度[m]-指标难度不断增加.m=|V(G)|2的情况也被广泛研究,Rajasingh等人证明了六边形网络,三维网格,以及网格,圆柱,圆环网络的过度指标.本文进一步计算了一些特殊图类的过度[m]-指标,例如单圈图,一些图的笛卡尔积图和直积图.
其他文献
氨氧化和甲烷氧化是碳氮循环中的重要步骤。直到现在,关于功能微生物的全球分布研究的来源序列都是公共数据库中基于PCR反应得到的,而PCR的引物偏向性会遗漏许多重要的微生物
随着工业发展,由于化石燃料的大量燃烧和人类活动加剧,大气CO2含量逐年增加,预计到本世纪末,全球大气CO2浓度将由380 ppm增加至750 ppm。由大气C02浓度升高导致的全球气候及
本研究运用细胞培养、MTS分析、RNA干扰、Western bloting等细胞学分子生物学技术和方法,以Raji细胞为实验对象,研究了PTEN活性与Akt信号转导在hsBAFF诱导B细胞增殖和存活中
多相感应电机系统相比于传统的三相电机,具有启动电流小、转矩脉动低,谐波损耗小,不需大量功率器件串联、冗余结构保证系统可靠性高等不可替代的优点,可使用低压功率器件实现
复杂网络作为生物系统、社会系统、交通网络、万维网等一系列复杂系统的抽象代表,其中的社团结构预示着网络中的节点聚合的趋势,所以社团结构是复杂网络的一个非常重要的属性
抗生素在日常生活中广泛应用,由于抗生素的广泛使用而引起的一系列的问题已经引起了许多研究者的关注.目前针对由于抗生素的不当使用而引发的病原体对抗生素的适应能力增强,
通常,为了得到正则的量子引力理论,我们需要将广义相对论表述成哈密顿形式,并引入超空间的概念,以得到Wheeler-DeWitt方程。但是超空间的Wheeler-DeWitt方程太过复杂,在不引
连通图G的两个顶点vi和vj之间的电阻距离rij定义为将图中任意两点间的距离用单位电阻赋值后构造出的电网络中根据欧姆定律计算出的节点vi和vj之间的有效电阻值.在电阻距离提
种群的扩散在自然界中普遍存在,一切生物过程的动态变化都受到随机波动的影响,研究种群的随机脉冲扩散模型具有十分重要的意义,许多生物数学学者对此已经做了大量的研究,在前
作为计量经济学的一个新的分支学科,空间计量经济学在近些年来发展迅速,越来越多的学者对其理论和应用进行了深入的探讨。空间计量经济学的基础是空间自回归模型,空间自回归