(0,mf-m+1)圖的正交(0,f)因子分解

摘要：設G是一個圖，f是定義在V(G)上的整數值函數，且對?坌x∈V(G)，有2k≤f(x)，設H1，H2，…，Hk是G的k個頂點不相交的子圖，且|E(Hi)|=m，1≤i≤k，證明了每個(0，mf-m+1)圖有一個(0，f)因子分解正交于Hi(i=1，2，…，k)。

關鍵詞：圖；因子；因子分解；正交因子分解

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2011)04-0820-01

Orthogonal (0，f) Factorizations of (0，mf-m+1) Graphs

LIU Jin-bo1，2， LIU Gang2， SUN Zhi-hong2

(1.College of Science， China University of Mining and Technology， Xuzhou 221008， China; 2.Department of Basic Cource Xuzhou Airforce College， Xuzhou 221000， China)

Abstract: Let G be a graph and f be an integer function defined on the vertices set V(G)， such that 2k≤f(x) for every vertex x∈V(G)， Let H1，H2，…，Hk be k vertex disjiont subgraphs of G such that |E(Hi)|=m，1≤i≤k，In this paper， it is proved that every (0，mf-m+1) graph G has a (0，f)factorizations Orthogonal to Hi， for i=1，2，…，k.

Key words: graph; factor; factorization; orthogonal factorization

本文所考慮的圖皆為有限無向簡單圖。設圖G是一個圖，分別用V(G)和E(G)表示圖G的頂點集和邊集，用dG(x)表示x在G中的次數。設g和f是定義在V(G)上的非負整數值函數，且對任一x∈V(G)，有g(x)≤f(x)。G的一個(g，f)-因子是指 的一個支撐子圖F，使得g(x)≤dF(x)≤f(x)對所有的x∈V(G)成立。若圖 的邊集能劃分為m個邊不交的(g，f)因子F1，F2，…，Fm，則稱F={F1，F2，…，Fm}是圖G的一個(g，f)-因子分解。具有m條邊的子圖稱為mˉ子圖。

文獻[3-1]給出了(mg+m-1，mf-m+1)-圖G有一個(g，f)-因子分解。文獻[2]已證明：設G是一個(0，mf-m+1)-圖，則對任意給定的m-子圖， 都有一個(0，f)-因子分解。文獻[3]已證明：若對任意x∈V(G)，都有2k≤f(x)，則每個(0，mf-m+1)圖G有一個(0，f)-因子分解。本文進一步研究了(0，mf-m+1)圖G的正交因子分解問題。證明如下結論：若對任意x∈V(G)，都有2k≤f(x)，則圖G的(0，f)-因子分解一定正交于k個頂點不相交的mˉ子圖。

1 預備引理

下面總假設G是一個(0，mf-m+1)-圖，設S，T是V（G）的不相交子集，用EG(S，T)表示G中連接S及T的邊集，記

引理1[1]：設G是一個(0，mf-m+1)-圖，f(x)是定義在V（G）上的非負整數函數，H是G的mˉ子圖，

則圖G有一個(0，f)因子分解正交于H。

引理2[2，4]：設G 是一個圖，g和f是定義在V(G)上的兩個整數值函數且對每個x∈V(G)有0≤g(x)

引理3[3，5]：設G是一個(0，mf-m+1)-圖，f(x)是定義在V（G）上的整數值函數且對每個x∈V(G)有2k≤f(x)，這里m≥2，k≥2是整數，則圖G有一個(0，f)因子F使得E1?哿E(F)且E2∩E(F)=Φ。

2 定理及證明

定理1：設G是一個(0，mf-m+1)-圖，f(x)是定義在V（G）上的整數值函數，設H1，H2，…，Hk是G的k個頂點不相交的mˉ子圖，則G有一個(0，f)因子分解正交于Hi(i=1，2，…，k)。

下面完成定理1的證明：

證明：當k=1時，由引理1知，定理顯然成立，故以下可假設k≥2當m=1時，定理顯然成立。

假設定理對m-1成立，這里m≥2，由引理3可知，G有一個(g，f)因子F1使得E1?哿E(F1)且E2∩E(F1)=Φ。由g(x)的定義知，F1也是G的一個含E1而不含E2的(0，f)因子。

令G'=G-E(F1)，根據g(x)的定義，有

因此，G'是一個(0，(m-1)f-(m-1)+1)圖。

令H'i=Hi-E1，1≤i≤k，根據歸納假設可知，G'有一個(0，f)因子分解F'={F2，…，Fm}正交于每個H'i， 1≤i≤k。于是，G有一個(0，f)因子分解F={F2，…，Fm}正交于每個Hi，1≤i≤k。

定理1證畢。

參考文獻：

[1] Alspach B，Heinrich K，Liu G. Contemporary Design Theory a Collection of Surveys[M].New York:wiley，1998:145-148.

[2] Liu G， othogonal (g，f)factoizations in graphs[J].D is crete Math: 1997:78-91.

[3] 劉金波，劉剛，王淑玲.(0，mf-m+1)圖的(0，f)因子分解[J].電腦知識與技術，2011(1).

[4] Liu G.othogonal (g，f)factoizations in graphs[J].D is crete Math，1997:104-110.

[5] Feng H.On orthogonal (0，f)factoizations [J].Actamath Scientia，1999，19:142-147.