高 煒,梁 立 ,夏幼明

(云南師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院,云南昆明 650092)

＊韌度與分?jǐn)?shù)k-消去圖

高 煒,梁 立 ,夏幼明

(云南師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院,云南昆明 650092)

分?jǐn)?shù)k-因子;分?jǐn)?shù)k-消去圖;韌度

O157.5

A

0 引言

1 預(yù)備知識(shí)

引理1[5]:設(shè)G是一個(gè)圖,k＞0為整數(shù),G是分?jǐn)?shù)k-消去圖當(dāng)且僅當(dāng)對(duì)任意S?V(G),T={x:x∈V(G)-S,dG-S(x)≤k}有k|T|-dG-S(T)≤k|S|-ε(S,T)其中

2 主要結(jié)論及證明

[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] 楊景波,康文明.分?jǐn)?shù)(g,f)-因子覆蓋圖和消去圖[C]//中國(guó)運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流論文集,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

國(guó)家自然科學(xué)基金(60903131);云南省教育廳科研基金(07Z40092)

高 煒(1981-),男,浙江紹興人,碩士研究生,主要從事圖論及其應(yīng)用研究.

book=365,ebook=298