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

ISOLATED TOUGHNESS AND FRACTIONAL k-COVERED GRAPHS

作　　者：李珍萍[1] 闫桂英[1] 章祥荪[1] 

机构地区：[1]中国科学院数学与系统科学研究院

出　　处：《应用数学学报》2004年第4期593-598,共6页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(60002001号);国家"973"信息技术与高性能软件基金资助项目

摘　　要：设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.

关 键 词：覆盖图 孤立韧度 K-因子 完全图 证明 分数 表示 首次 关系 研究 

分 类 号：O157.5[理学—数学]