高煒

（1.蘇州大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，江蘇 蘇州 215006；2.云南師范大學(xué) 信息學(xué)院，云南 昆明 650092）

＊韌度與分?jǐn)?shù)（k，n′）－臨界消去圖

高煒1，2

（1.蘇州大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，江蘇 蘇州 215006；2.云南師范大學(xué) 信息學(xué)院，云南 昆明 650092）

圖；韌度；分?jǐn)?shù)臨界圖；分?jǐn)?shù)臨界消去圖

若去掉G中的任意n′個頂點(diǎn)的剩余子圖仍有一個分?jǐn)?shù)k－因子，則稱此圖為分?jǐn)?shù)（k，n′）－臨界圖.若去掉G中的任意一條邊的剩余圖仍有分?jǐn)?shù)k－因子，則稱G為分?jǐn)?shù)k－消去圖.一個圖G稱為分?jǐn)?shù)（k，n′）－臨界消去圖，若去掉G中的任意n′個頂點(diǎn)的剩余子圖仍是分?jǐn)?shù)k－消去圖.

Chvátal［2］首次引入韌度的概念：若G是完全圖，則t（G）＝∞.若G不是完全圖，

這里ω（G－S）表示G－S的連通分支數(shù).在下文中，我們用n表示圖G的頂點(diǎn)個數(shù).關(guān)于韌度與分?jǐn)?shù)因子、分?jǐn)?shù)消去圖、分?jǐn)?shù)臨界圖的關(guān)系，［3－5］做了研究，部分重要結(jié)果如下.

特別地，當(dāng)g（x）＝a，f（x）＝b且a＝b＝k時有

引理4［6］設(shè)G是一個圖，k≥1是正整數(shù).設(shè)n′為非負(fù)整數(shù).G是分?jǐn)?shù)（k，n′）－臨界消去圖當(dāng)且僅當(dāng)對任意滿足｜S｜≥n′的V（G）的不交子集S，T成立.

主要結(jié)論的證明

下面我們給出定理4的詳細(xì)證明，其證明思路主要參考文獻(xiàn)［4］.

定理4的證明當(dāng)G是完全圖時，t（G）＝∞.但由頂點(diǎn)數(shù)條件，易知G是分?jǐn)?shù)（k，n′）－臨界消去圖.下面設(shè)G不是完全圖.另外，n′＝0的情況即為定理2，因此不妨假設(shè)n′≥1.

設(shè)G滿足定理4的條件但不是分?jǐn)?shù)（k，n′）－臨界消去圖.顯然，T≠?，否則ε（S，T）＝0且（1）成立.由引理4知，存在不交的S，T滿足

［1］ Bondy J A，Mutry U S R.Graph Theory［M］.Berlin：Spring，2008.

［2］ Chvátal V.Tough Graphs and Hamiltonian Circuits［J］.DiscreteMath，1973，5：215－228.

［3］ Liu G，Zhang L.Toughness and the Existence of Fractionalk－factors of Graphs［J］.DiscreteMath，2008，308：1741－1748.

［4］ 高煒，梁立，夏幼明.韌度與分?jǐn)?shù)k－消去圖［J］.山西大學(xué)學(xué)報：自然科學(xué)版，2010，33（3）：358－365.

［5］ Liu Shu－li.On Toughness and fractional（g，f，n）－critical Graphs［J］.InformationProcessingLetters，2010，110：378－382.

［6］ 高煒.關(guān)于分?jǐn)?shù)消去圖的若干結(jié)果［D］.蘇州：蘇州大學(xué)博士學(xué)位論文，2012.

Toughness and Fractional（k，n′）－critical Deleted Graphs

GAO Wei1，2
（1.DepartmentofMathematics，SoochowUniversity，Suzhou215006，China；
2.DepartmentofInformation，YunnanNormalUniversity，Kunming650092，China）

graph；toughness；fractional critical graph；fractional critical deleted graph

O157

A

0253－2395（2012）04－0626－06＊

2012－01－10；

2012－03－23

國家自然科學(xué)基金（11071223）

高煒（1981－），男，浙江紹興人，博士，講師，主要從事圖論、統(tǒng)計(jì)學(xué)習(xí)理論的研究.