图的相对断裂度的若干结果

文献［１］引入了图的相对断裂度的概念，讨论了相对断裂度与１－因子和带宽的关系，并在文献［１］的基础上进一步刻划了相对断裂度与图的结构     

图的最小符号控制函数的充要条件

在图G=（V,E）的顶点集V上定义一个二值函数f=V→{-1,1},使对任何v∈V,f(N[v])≥1,则称f是图G的一个符号控制函数。图的符号控制函数的权重定义为f(V)=∑v∈vf(V),它的最小权重称为图的符号控制数,记为γs(G）达到最小权重的符号控制函数称为图的最小符号控制函数,本文讨论最小符号控制函数的必要条件。