高炜

(云南师范大学信息学院，云南昆明650092)

分数(g，f，n'，m)－临界消去图的2个充分条件

高炜

(云南师范大学信息学院，云南昆明650092)

设G是一个图，若去掉G中的任意n'个顶点的剩余子图仍是分数(g，f，m)-消去图，则称G是一个分数(g，f，n'，m)-临界消去图.从独立数和度条件2个角度出发，分别给出了图G是分数(g，f，n'，m)-临界消去图的2个充分条件.

图;分数临界图;分数临界消去图

1 预备知识

本文只考虑无向、简单、有限图.文中涉及的符号和标记若没有特别说明，则与文献［1］一致.设G是一个图，具有顶点集V(G)和边集E(G).顶点x的度和最小度分别记为dG(x)和δ(G).令S和T是V(G)的任意2个不相交的子集.EG(S，T)表示一个顶点在S中而另外一个顶点在T中的G的边集合.记eG(S，T)= EG(S，T)，dG-S(T)=dG(T)-eG(S，T)且dG-T(S)=dG(S)-eG(S，T).设g和f分别是定义在V(G)上的2个整数值函数且对每个x∈V(G)有g(x)≤f(x).分数(g，f)-示性函数h是一个函数分配给图G的每一条边一个［0，1］之间的数，使得对每一个点x∈V(G)有g(x)≤dGh(x)≤f(x)，其中dGh(x)=∑e∈Exh(e)是点x∈V(G)的分数度，且Ex={e:e=xy∈E(G)}.设h是图G的分数(g，f)-示性函数.令Eh= {e:e∈E(G)，h(e)≠0}.若Gh是G的支撑子图使得E(Gh)=Eh，则Gh称为G的分数(g，f)-因子.若去掉G中的任意n'个顶点的剩余子图仍有分数(g，f)-因子，则称G为分数(g，f，n')-临界图.若去掉G中的任意m条边的剩余子图仍有分数(g，f)-因子，则称G为分数(g，f，m)-消去图.一个图G称为分数(g，f，n'，m) -临界消去图，若去掉G中的任意n'个顶点的剩余子图仍是分数(g，f，m)-消去图.

文献［2］给出了一个图有分数f-因子的独立数和最小度条件.

定理1［2］设G是一个连通图，a≤b为非负整数，f(x)是定义在V(G)上的整数值函数使得对于所有的x∈V(G)都有a≤f(x)≤b.如果δ(G)≥b，独立数，则G有分数f-因子.

文献［3］给出了图有分数(g，f)-因子的一个度条件……