超圖的奇圈橫貫

朱俊杰

(昌吉學(xué)院數(shù)學(xué)系,新疆昌吉 831102)

超圖的奇圈橫貫

朱俊杰

(昌吉學(xué)院數(shù)學(xué)系,新疆昌吉 831102)

1997年,C.Berge提出了圖 G奇圈橫貫的定義,并用圖G+K2研究了圖G的奇圈橫貫,最后得出結(jié)論, τ=n—-α(G+K2).將圖 G的奇圈橫貫推廣到超圖H上,并引入新概念 H+K2,得到超圖 H的兩個頂點x和z之間有奇長鏈的充分條件.

超圖;奇圈橫貫;H+K2

1 基本概念

定義1 令X=(x1,x2,…,xn)是一個有限集,關(guān)于 X上的一個超圖,H=(E1,E2,…,Em),是 X上一個有限子集簇,使得,

同時,一個超圖,H=(E1,E2,…,Em),若還滿足,

則稱 H為簡單超圖.

對 j∈{1,2,…,m},r(H)=max|Ej|稱為 H的秩,s(H)=min|Ej|稱為 H的下秩.如果,r(H) =s(H),則稱 H是一致超圖.秩為 r的簡單一致超圖稱為r-一致超圖.

定義2 在超圖H=(E1,E2,…,Em)中,一條長q鏈的鏈是指滿足以下條件的序列(x1,E1,x2, E2,…,xq,Eq,xq+1).

(1)x1,x2,…,xq是H中不同的頂點;

(2)E1,E2,…,Eq是H中不同的邊;

(3)對 k=1,2,…,q,xk,xk+1∈Ek.

若q＞1,且xq+1=x1,那么稱這樣的鏈為 H的q長圈.q為奇數(shù)稱為奇圈,q為偶數(shù)稱為偶圈.

定義3 對集合A?X,稱HA=(Ej∩A|1≤j≤m,Ej∩A≠φ)為A對H的導(dǎo)出超圖.對集合J?{1,2,…,m},稱 H′=(Ej|j∈J)為J對H誘導(dǎo)的部分超圖.H′的頂點集是X的一個非空子集.

2 超圖的奇圈橫貫

定義4 H是一個超圖,復(fù)制H形成H′,a為H中任意一個頂點,a′是H′中對應(yīng)a的頂點,用一條邊連接a和a′,形成的超圖我們稱之為H+K2.連接a和a′的邊叫頂點邊.

定義5 超圖的匹配是超圖中兩兩不相交的邊組成的集合,集合中的元素稱為匹配邊.用v(H)表示 H的最大匹配的邊數(shù).設(shè) a是超圖中的一個頂點,若 a包含在超圖的一條匹配邊e中,則稱a是飽和的,也稱e覆蓋a.若超圖中存在一個匹配滿足其中的元素覆蓋超圖中的所有頂點則稱這個匹配是超圖,且是完美匹配.

定理1 H是連通簡單超圖,x和z是H中的兩個頂點,若超圖,H+K2-{x′,z′},存在有完美匹配,則 H中有一條x到z的奇長鏈.

證明 設(shè)H+K2-{x′,z′}中有完美匹配M,那么稱這個完美匹配中的邊為粗邊,H中其他邊稱之為細邊,下面做一條 x到z的奇長鏈.

因為H+K2-{x′-z′}中有完美匹配,存在一個頂點x1,使得x,x1在 H+K2-{x′,z′}的一條粗邊中,記為 E1(E1∈H),且這是唯一包含 x的粗邊(若d(x1)=1,則x1在H+K2-{x′,z′}也要飽和,那么包含 x′1的粗邊只能是 E′1-x),頂點邊 x1x′1必不在M中,否則與匹配矛盾.那么,存在一個頂點x2,使得x′1,x′2在H+K2-{x′,z′}的一條粗邊中,記為(∈H′).同理,x2是頂點邊的另一個端點,存在一個頂點 x3,使得 x2,x3在 H+K2-{x′,z′}的一條粗邊中,記為 E3(E3∈H).如此,則形成一個奇長邊序列,E1,E2,…,Ek,其中,x∈E1, z∈Ek,Ei∩Ei+1≠?,這里,Es(s為偶數(shù))是 E′s在H中的對應(yīng)邊.

下證 Ei(I=1,2,…,k)是不同的邊.

假設(shè)存在 Ei= Ej,(i＜j,i,j=0,1,2,…,k),設(shè) xi1,xi2∈Ei,xi1,xi2∈{xi|i=1,2,…,k-1}, xi1∈Ei-1∩Ei,xi2∈Ei∩Ei+1和 xj1,xj2∈Ej,xj1, xj2∈{xj|j=1,2,…,k-1},xj1∈Ej-1∩Ej,xj2∈Ej∩Ej+1,由假設(shè) xi1,xi2,xj1,xj2∈Ei= Ej.當 i,j奇偶性相同時,在 H+K2-{x′,z′}中,Ei,Ej要么同在 H中,要么同在 H′中,在奇長邊序列 E1,E2,…,Ek中,用 xj2代替 xi2,去掉 Ei+1,…,Ej仍然可得x到z的一個奇長序列.當i,j奇偶性不同時,在H+ K2-{x′,z′}中,Ei,Ej一個在H中,一個在 H′中,不妨設(shè) Ei∈H,Ej∈H′,由假設(shè) xj2∈Ei,且 xj2∈Ej+1,因為在 H+K2-{x′,z′}中 Ei,Ej+1都是 H中的粗邊,若 Ei≠Ej+1,則xj2被兩條不同粗邊包含,與匹配定義矛盾,因此 Ei=Ej+1.所以,在奇長邊序列E1,E2,…,Ek中,用 xj2+1代替 xi2,去掉 Ei+1,…,Ej+1仍然可得 x到z的一個奇長序列.

由上述過程可看出,若 Ei,(i=1,2,…,k)中有相同的邊,總可以去掉一些邊使其變得更短且不改變其奇偶性,而 x和z之間的距離不可能無限短,因此存在奇長邊序列 Ei,(i=1,2,…,k),它連接x和z,且是不同的邊.

再證 x=x0,x1,x2,…,xk-1,xk=z是不同的點.

假設(shè)存在 xi= xj,(i≠j,i,j∈{0,1,2,…, k}),由 H+K2-{x′,z′}的性質(zhì)知,在 H+K2-{x′,z′}中必存在H中的兩條粗邊包含xi和xj.由以上證明可知,這是兩條不同的粗邊,由于 xi=xj,(i≠j,i,j∈{0,1,2,…,k}),那么,xi被兩條粗邊包含,這與匹配的定義矛盾.因此,x=x0,x1,x2,…, xk-1,xk= z是不同的點.

此也證明了 H中存在一條x到z的奇長鏈.

定義6 設(shè)H=E1,E2,…,Em是一個超圖,整數(shù) k≥2.H的一個頂點k-著色是指對X的一個k-劃分,使得 H的每條非環(huán)的邊至少與兩個類相交,即,

E∈H,|E|＞1?E■Si,(i=1,2,…,k)

Si中的頂點稱為i色頂點.Si允許是空集,故只有環(huán)是單色邊.使超圖H有k著色的最小正整數(shù)k稱為 H的色數(shù),記為χ(H).

定義7 設(shè)超圖H=(E1,E2,…,Em),則=,…,),其中?Ei,(i=1,2,…,m)稱為H的子超圖.若H任意的子簡單超圖都是兩可

著色的,則稱 H具有遺傳兩可著色性質(zhì).

定義8 設(shè) H=(E1,E2,…,Em)是 H上的超圖,若集合 T?X與H中每條邊相交,即,

則稱 T是H的橫貫.

定義9 超圖H的奇圈橫貫是一個頂點集滿足與超圖中所有奇圈相交非空.基數(shù)最小的超圖奇圈橫貫稱之為超圖的最小奇圈橫貫,它的基數(shù)記為τ′(H).不包含 H中任何奇圈的頂點集稱為超圖的奇圈獨立集,基數(shù)最大的超圖奇圈獨立集稱為超圖的最大奇圈獨立集,它的基數(shù)記為α′(H),顯然有, τ′(H)=n-α′(H).H不包含任何基數(shù)大于1的邊的頂點集稱為 H的一個獨立集,基數(shù)最大的獨立集稱為最大獨立集,它的基數(shù)記為α(H).

定理2 若n個頂點的超圖H具有遺傳兩可著色性質(zhì),那么,

τ′(H)=n-α(H+K2).

證明 設(shè)H的最小奇圈橫貫為X-D,存在S, T滿足,D=S∪T和S∩T≠?,由H具有遺傳兩可著色性質(zhì)的定義,S∪T在H中的導(dǎo)出子超圖是兩可著色的.因此,S和T中都不包含H中的邊.設(shè)在H+K2中,T′是T(∈H)在H′的像,那么S∪T′不包含H+K2中的H和H′,又因為S∩T=?,那么S∪T′不包含H+K2中的頂點邊,所以S∪T′是 H+K2的一個頂點獨立集.因為|S∪T′|=|S∪T|和|S∪T′|≤α(H+K2),故

另外,設(shè)S∪T′為H+K2的一個最大頂點獨立集,其中,S∈H,設(shè) T是T′在H中的像,S和T中都不包含H中的邊,所以S∪T在H中的導(dǎo)出子超圖是兩可著色的,那么S∪T在H中的導(dǎo)出子超圖不包含奇圈,否則假設(shè)S∪T在H中的導(dǎo)出子超圖包含奇圈,不妨設(shè)為 x1,E′1,x2,E′2,…,xk,E′k,x1,那么G={x1x2,x2x3,…,xkx1}是這個奇圈的子超圖,所以G也是H的子超圖,又因為H具有遺傳兩可著色性質(zhì),所以G={x1x2,x2x3,…,xkx1}是兩可著色的,但 G是奇圈,所以一定不會兩可著色,矛盾.

因此,S∪T也不包含H的奇圈,故,S∪T是H的一個奇圈獨立集.

由于τ′(H)=n-α′(H),且|S∪T|≤α′(H),因此,

綜上所述,

[1]Berge C.Hypergraphs：Combinatorics of Finite Sets[M].North Holland：Amsterdam,1973.

[2]Berge C,Fouquet J I.Odd the optimal transversals of the odd cycles[J].Discrete Mathematics,1997,169(2)：169-175.

[3]K ostochka A,Verstraete J.Even cycles in hypergraph[J].Journal of Combinatorial Theory(Series B),2005,94(1)：173-182.

[4]Dacar F.The cyclicity of a hypergraph[J].Discrete Mathematics,1998,182(1)：53-67.

[5]Gyárfás A,Jacobson M S,K zdy A E,et al.Odd cycles andθ-cycles in hypergraphs[J].Discrete Mathematics,2006,306(19-20)：2481-2491.

[6]BondyJ A.Theory with Applications[M].New Y ork：Macmillan Press,1976.

[7]Vishwanathans S.On2-coloring k-uniform hypergraphs[J]. Journal of Combinatorial Theory(Series A),2003,101(2)：168 -172.

[8]Acharya B D.Even Edge Colorings of a Graph[J].Journal of Combinatorial Theory(Series B),1983,35(1)：78-79.

[9]Alon N.Even Edge Colorings of a Graph[J].Journal of Combinatorial Theory(Series B),1985,38(2)：93-94.

[10]WangJianfang.Paths and cycles of hypergraphs[J].Science in China(Series A),1999,42(1)：1-12.

Odd Cycles Transversals of Hypergraphs

ZHU Junjie

(Department of Mathematics,Changji College,Changji 831102,China)

In 1997,C.Berge proposed the concept of the transversals of the odd cycles of Gin the second reference and made use of the graph G+K2to study the transversals of odd cycles of G,and gained the conclusion ofτ=n-α(G+K2).In this paper,the concept was promoted to hypergraph H and a new definition of the transversals of the odd cycles H+K2was formed.The sufficient conditions that an odd chain from the vertex x to the vertex z exists in H were obtained.

hypergraph;transversals of the odd cycles;H+K2

O157.5

：A

1004-5422(2010)02-0124-03

2010-01-25.

朱俊杰(1982—),男,碩士研究生,從事圖論研究.