论文部分内容阅读
设图G=(V(G),E(G)),V(G)和E(G)分别表示图G的顶点集和边集,n=|V(G)|记作图G的阶数.对M(包含或等于)E(G),若M中任意两条边在G中是不相邻的,则称M是G的匹配.G的所有匹配的最大势称为G的匹配数,记作α(G).显然,α(G)≤|V(G)|/2.设D(包含或等于)V(G),若V(G)中的每一个顶点均至少与D的某一个顶点相邻接,也即N(D)=V(G),则称D为G的全控制集.如果对任意的w∈D,都使得D{w}不再是G的全控制集,则称D为G的极小全控制集.G的所有极小全控制集的最小势称为G的全控制数(或者称为下全控制数),记为γt(G).设D(包含或等于)V(G),对每一个u∈VD,(a)若|N(u)∩D|≥1,则称D是G的控制集;(b)若|N(u)∩D|=1,则称D是G的完美控制集.当D是G的完美控制集且为G的点独立集时,称D为G的独立完美控制集或有效控制集.本文主要工作分两部分.第一部分,我们从图最小度的角度研究了图的全控制数和匹配数之间的可比较性.指出当图的最小度不超过2时,对一般图G而言,它的匹配数α(G)与全控制数γt(G)是不可比较的(我们刻划了具体的几类图来说明).2000年,Favaron在研究全控制数的界时,猜想对任意最小度不小于3的简单图G,其全控制数不超过图阶数的一半.本文证明了对任意k-正则无爪图G,k≥3,有γt(G)≤α(G).从这一定理出发,显然可推论得知对k-正则无爪图,k≥3,Favaron猜想是正确的.第二部分,我们主要讨论了图的完美控制集(数)和有效控制集.先证明了无向循环图一定存在有效控制集.然后,建立了单圈图的完美控制数的一个上界,并刻划了达到这一上界的单圈图类,故这一上界是最好可能的.从这一结果出发,可知对树而言增加一条边并不会使其完美控制数显著增加.