一类特殊坚韧图的性质

连通图G的坚韧度定义为。如果G的坚韧度是t,并且删去G的任意一条边后其坚韧度减小,则称G是极小t-坚韧的。Matthews等证明了K1,3-free图的连通度是其坚韧度的2倍。本文证明了坚韧度为t的K1,n-free图的连通度不超过(n-1)t,且极小1-坚韧,K1,4-free图的连通度为2。此外,Kriesell猜想极小1-坚韧图的最小度是2。Katona等推广了上述猜想,极小t-坚韧图的最小度是 。本文证明了极小1/(n-1)-坚韧,K1,n-free图的最小度为1,其中n≥3。

K_(1,n)—free图的f—因子

图G称为K1,n—free,若图G不包含同构于K1,n的导出子图 .设 f(x)是定义在V(G)上的非负整数函数 ,G的一个支撑子图F称为G的一个f—因子 ,若对任意的ν∈V(G)有dF(ν) =f(ν) .对K1,n—free图存在f—因子涉及到最小度条件进行了研究 ,得到了一个充分条件 .有关定理为本定理的特例 .

K_(1,n)-free图有(g,f)-因子的最小度条件

讨论了图的(g,f)-因子存在问题,并给出了K1,n-free图有(g,f)-因子的一个最小度条件。

K_(1,n)-free图具有给定性质的[a,b]-因子的一个充分条件

图G称为K1,n-free图,如果它不含K1,n作为其导出子图.对K1,n-free图具有给定性质的[a,b]-因子涉及到最小度条件进行了研究,得到一个充分条件.