＊ 韧度与分数k-消去图

高 炜,梁 立 ,夏幼明

(云南师范大学计算机科学与信息技术学院,云南昆明 650092)

＊韧度与分数k-消去图

高 炜,梁 立 ,夏幼明

(云南师范大学计算机科学与信息技术学院,云南昆明 650092)

分数k-因子;分数k-消去图;韧度

O157.5

A

0 引言

1 预备知识

引理1[5]:设G是一个图,k＞0为整数,G是分数k-消去图当且仅当对任意S⊆V(G),T={x:x∈V(G)-S,dG-S(x)≤k}有k|T|-dG-S(T)≤k|S|-ε(S,T)其中

2 主要结论及证明

[1] BONDY J A,MURTY U SR.Graph Theory with Applications[M].New York:Macmillan Press Lid,1976.

[2] SCHEINERMAN E R,ULLMNA D H.Fractional Graph Theory[M].New York:John Wiley and Sons,1997.

[3] YANGJing-bo.Fractional(g,f)-covered Graph and Fractional(g,f)-deleted Graph[C]//Proceedings of the Sixth National Conference of Operation Research Society of China[D].Shanghai:Shanghai University press,2000.

[4] CHVA TAL V.Tough Graphs and Hamiltonian Circuits[J].Discrete Math,1973,5:215-228.

[5] 杨景波,康文明.分数(g,f)-因子覆盖图和消去图[C]//中国运筹学会第六届学术交流论文集,Global-Link出版社,2000:450-454.

[6] LI Zhen-ping,YAN Gui-ying,ZHANG Xiangsun.Isolated Toughness and Fractionalk-deleted Graphs[J].OR Transactions(in Chinese),2003,7(4):79-85.

[7] YU Ji-guo,WANGNa,BIAN Qiu-ju,et a l.Some Resultson Fractional Deleted Graphs[J].OR Transactions(in Chinese),2007,11(2):65-72.

[8] CHVA TAL V.Tough Graphs and Hamiltonian Circuits[J].Discrete Mathematics,1973,5:215-228.

[9] LIU Gui-zhen,ZHANG Lan-ju.Toughness and the Existence of Fractionalk-factors of Graphs[J].Discrete Mathematics,2008,308:1741-1748.

Toughness and Fractional k-deleted Graphs

GAO Wei,LIANG Li,XIA You-ming
(School of Computer Science and Information Technology,Yunnan Normal University,Kunming650092,China)

fractionalk-factor;fractionalk-deleted graph;toughness

0253-2395(2010)03-0358-08＊

2009-10-26

国家自然科学基金(60903131);云南省教育厅科研基金(07Z40092)

高 炜(1981-),男,浙江绍兴人,硕士研究生,主要从事图论及其应用研究.

book=365,ebook=298