分?jǐn)?shù)(g，f，n'，m)－臨界消去圖的2個充分條件

高煒

(云南師范大學(xué)信息學(xué)院，云南昆明650092)

分?jǐn)?shù)(g，f，n'，m)－臨界消去圖的2個充分條件

高煒

(云南師范大學(xué)信息學(xué)院，云南昆明650092)

設(shè)G是一個圖，若去掉G中的任意n'個頂點(diǎn)的剩余子圖仍是分?jǐn)?shù)(g，f，m)-消去圖，則稱G是一個分?jǐn)?shù)(g，f，n'，m)-臨界消去圖.從獨(dú)立數(shù)和度條件2個角度出發(fā)，分別給出了圖G是分?jǐn)?shù)(g，f，n'，m)-臨界消去圖的2個充分條件.

圖;分?jǐn)?shù)臨界圖;分?jǐn)?shù)臨界消去圖

1 預(yù)備知識

本文只考慮無向、簡單、有限圖.文中涉及的符號和標(biāo)記若沒有特別說明，則與文獻(xiàn)［1］一致.設(shè)G是一個圖，具有頂點(diǎn)集V(G)和邊集E(G).頂點(diǎn)x的度和最小度分別記為dG(x)和δ(G).令S和T是V(G)的任意2個不相交的子集.EG(S，T)表示一個頂點(diǎn)在S中而另外一個頂點(diǎn)在T中的G的邊集合.記eG(S，T)= EG(S，T)，dG-S(T)=dG(T)-eG(S，T)且dG-T(S)=dG(S)-eG(S，T).設(shè)g和f分別是定義在V(G)上的2個整數(shù)值函數(shù)且對每個x∈V(G)有g(shù)(x)≤f(x).分?jǐn)?shù)(g，f)-示性函數(shù)h是一個函數(shù)分配給圖G的每一條邊一個［0，1］之間的數(shù)，使得對每一個點(diǎn)x∈V(G)有g(shù)(x)≤dGh(x)≤f(x)，其中dGh(x)=∑e∈Exh(e)是點(diǎn)x∈V(G)的分?jǐn)?shù)度，且Ex={e:e=xy∈E(G)}.設(shè)h是圖G的分?jǐn)?shù)(g，f)-示性函數(shù).令Eh= {e:e∈E(G)，h(e)≠0}.若Gh是G的支撐子圖使得E(Gh)=Eh，則Gh稱為G的分?jǐn)?shù)(g，f)-因子.若去掉G中的任意n'個頂點(diǎn)的剩余子圖仍有分?jǐn)?shù)(g，f)-因子，則稱G為分?jǐn)?shù)(g，f，n')-臨界圖.若去掉G中的任意m條邊的剩余子圖仍有分?jǐn)?shù)(g，f)-因子，則稱G為分?jǐn)?shù)(g，f，m)-消去圖.一個圖G稱為分?jǐn)?shù)(g，f，n'，m) -臨界消去圖，若去掉G中的任意n'個頂點(diǎn)的剩余子圖仍是分?jǐn)?shù)(g，f，m)-消去圖.

文獻(xiàn)［2］給出了一個圖有分?jǐn)?shù)f-因子的獨(dú)立數(shù)和最小度條件.

定理1［2］設(shè)G是一個連通圖，a≤b為非負(fù)整數(shù)，f(x)是定義在V(G)上的整數(shù)值函數(shù)使得對于所有的x∈V(G)都有a≤f(x)≤b.如果δ(G)≥b，獨(dú)立數(shù)，則G有分?jǐn)?shù)f-因子.

文獻(xiàn)［3］給出了圖有分?jǐn)?shù)(g，f)-因子的一個度條件.

定理2［3］設(shè)G是1個圖.如果對于任意的1對頂點(diǎn)v，w∈V(G)都有

則G有分?jǐn)?shù)(g，f)-因子.

文獻(xiàn)［4］將上述2個結(jié)論推廣到分?jǐn)?shù)(g，f，n')-臨界圖的情形，得到了如下結(jié)論.

定理4［4］設(shè)G是1個圖，a，b和n'是非負(fù)整數(shù)，a≤b.設(shè)g(x)和f(x)是定義在V(G)上的非負(fù)整值函數(shù)且滿足對任意的x∈V(G)都有a≤g(x)≤f(x)≤b.若對于任意的1對頂點(diǎn)v，w∈V(G)，都有

則G是分?jǐn)?shù)(g，f，n')-臨界圖.

本文將文獻(xiàn)［4］中結(jié)果推廣到分?jǐn)?shù)(g，f，n'，m)-臨界消去圖的情形，證明了如下2個結(jié)論.

定理6設(shè)G是1個圖，a，b，n'和m是非負(fù)整數(shù)，a≤b.設(shè)g(x)和f(x)是定義在V(G)上的非負(fù)整值函數(shù)且滿足對任意的x∈V(G)都有a≤g(x)≤f(x)≤b.若對于任意的1對頂點(diǎn)v，w∈V(G)，都有則G是分?jǐn)?shù)(g，f，n'，m)-臨界消去圖.

可見，在定理5和定理6中分別令m=0，即得定理3和定理4.此外，在定理5中，如果對于任意的x∈V(G)都有f(x)=g(x)，則可得如下推論.

在推論1中，如果n'=0，則可得如下推論.

在定理6中，如果對于任意的x∈V(G)都有f(x)=g(x)，則可得如下推論.

推論3設(shè)G是1個圖，a，b，n'和m是非負(fù)整數(shù)，a≤b.設(shè)f(x)是定義在V(G)上的非負(fù)整值函數(shù)且滿足對任意的x∈V(G)都有a≤f(x)≤b.若對于任意的1對頂點(diǎn)v，w∈V(G)，都有

則G是分?jǐn)?shù)(f，n'，m)-臨界消去圖.

在推論3中，如果n'=0，則可得如下推論.

推論4設(shè)G是1個圖，a≤b是非負(fù)整數(shù)，m≥0是整數(shù).設(shè)f(x)是定義在V(G)上的非負(fù)整值函數(shù)且滿足對任意的x∈V(G)都有a≤f(x)≤b.若對于任意的1對頂點(diǎn)v，w∈V(G)，都有

則G是分?jǐn)?shù)(f，m)-消去圖.

為證明定理5和定理6，我們需要引入引理1作為己知結(jié)論.

引理1［5］設(shè)G是1個圖，g，f是定義在頂點(diǎn)集上的2個非負(fù)整值函數(shù)滿足對所有x∈V(G)有g(shù)(x)≤f(x).設(shè)n'，m為非負(fù)整數(shù).G是分?jǐn)?shù)(g，f，n'，m)-臨界消去圖當(dāng)且僅當(dāng)

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

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

定理5的證明設(shè)G滿足定理5的條件但不是分?jǐn)?shù)(g，f，n'，m)-臨界消去圖.顯然，T≠?，否則(1)成立.由引理1知，存在不交的S，T滿足

其中S≥n'.選擇S，T使T最小.從而，dG-S(T)≤b-1對所有x∈T成立.否則，若存在x∈T使得dG-S(x)≥b，則子集S，T{x}同樣滿足(2).這與S，T的選取矛盾.

設(shè)d=min{ dG-S(x)x∈T}，則

由于T≠?，我們可構(gòu)造T的序列x1，x2，…，xk如下:取x1∈T使得x1是G［T］中度最小的頂點(diǎn).設(shè)N1=NG［x1］∩T且T1=T.對于i≥2，如果∪＜iNj≠φ，設(shè)Ti=T-∪＜iNj.取xi∈Ti使得xi是G［Ti］中度最小的頂點(diǎn)，設(shè)Ni=NG［xi］∩Ti.繼續(xù)這個過程直到對某個i，使得Ti=?，記i=k+1.從而可知x1，x2，…，xk是G的獨(dú)立集.因為T≠?，所以k≥1.

設(shè)Ni=ni.由Ni的定義，可以得到下列性質(zhì).

結(jié)合(2)，(5)，(7)可得

矛盾.從而結(jié)論成立.

定理6的證明設(shè)G滿足定理6的條件但不是分?jǐn)?shù)(g，f，n'，m)-臨界消去圖.顯然，T≠?.由引理1知，存在不交的S，T滿足

由如上不等式可得矛盾.從而結(jié)論成立.

其中Kib是有b個頂點(diǎn)的完全圖(1≤i≤k+1).

因此可知G不是分?jǐn)?shù)(g，f，n'，m)-臨界消去圖.

［1］BONDY J A，MUTRY U S R.Graph theory［M］.Berlin:Springer-Verlag，2008.

［2］CAI J，LIU G，Degree and stability number condition for the existence of connected factors ingraphs［J］.J Appl Math Comput，2009，29:349-356.

［3］LIU G，ZHANG L.Maximum fractional(0，f)-factors of graphs［J］.Mathematica Applicata，2000，13:31-35.

［4］劉紅霞.圖參數(shù)與圖的因子［D］.濟(jì)南:山東大學(xué)，2010.

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

(責(zé)任編輯萬志瓊)

Two Sufficient Conditions for(g，f，n'，m)Critical Deleted Graph

GAO Wei
(School of Information，Yunnan Normal University，Kunming 650092，China)

Supposing graph G is a fractional(g，f，n'，m)critical deleted graph，if after deleting any n'vertices of G，the remaining graph is a fractional(g，f，m)deleted graph.Taking the independent number and degree condition into consideration，the paper gives two sufficient conditions for the fractional(g，f，n'，m)critical deleted graph.

graph;fractional critical graph;fractional critical deleted graph

O 157

A

1672-8513(2012)04-0273-04

10.3969/j.issn.1672-8513.2012.04.011

2011-12-22.

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

高煒(1981-)，男，博士，講師.主要研究方向:圖論、統(tǒng)計學(xué)習(xí)理論.