图的孤立韧度与分数k-覆盖图

ISOLATED TOUGHNESS AND FRACTIONAL k-COVERED GRAPHS

设G是一个图,若对于图G的任一条边e,都存在一个分数k-因子h,使得h(e)=1,则称图G是分数k-覆盖图.图G的孤立韧度I(a)定义为:若G是完全图,则I(C)=+∞;否则,I(G)=min{|S|/i(G-S):SCV(G),i(G-S)≥2},其中i(G-S)表示G-S中的孤立点数目.本文首次提出并研究了一个图是分数k-覆盖图与它的孤立韧度之间的关系,证明了当I(G)>k,并且δ(G)>k+1时,G是分数k-覆盖图.我们还证明了,这个结果是最好可能的.

A graph G is fractional k-covered if for each edge e of G, there exist a fractional k- factor h, such that h(e) = 1. The isolated toughness I(G) of a graph G is defined as follows: If G is a complete graph, then I(G) = +00; else, I(G) = min {|s|/i(G-S):S V(G), i(G -S) > 2}, where i(G - S) denotes the number of isolated vertices in G - S. In this paper, we bring forward and investigate for the first time the relationship between the fractional k-covered and the isolated toughness of a graph, we have proved that G is fractional k- covered if δ(G) > k + 1 and I(G) > k. We have also proved that our result is the best possible.