均衡的完全3-部3-一致超圖的單色放松路劃分

李婷婷 張 霞

( 山東師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,250358,濟(jì)南 )

1 引 言

路劃分問題起源于Gerencsér和Gyárfás[1](1967年)提出的一個基本的命題: 對于n個頂點(diǎn)的完全圖Kn的任意的一個2-邊染色, 它的頂點(diǎn)集V(Kn)可以被劃分成一條紅色路和一條藍(lán)色路. 這里的空集和單點(diǎn)可以看作是染任意顏色的一條路. 1979年，Lehel猜想用圈代替上述命題中的路結(jié)論仍然成立. 對于n很大時Lehel猜想在文獻(xiàn)[2]和[3]中被證實(shí), 并且在2010年由Bessy和Thomassé[4]證得對所有的n都成立.

對于超圖的情形, 本文先介紹論文中所用的一些基本概念和相關(guān)符號表示, 若未提及的概念和符號表示請參考文獻(xiàn)[5]和[6].

一個k-一致超圖H, 有l(wèi)條超邊e1,e2,e3,…,el滿足對任意的i∈[l-1], 有|ei∩ei+1|=1并且對于2≤i+1

圖G(或超圖H)的一個邊染色是從邊集E(G)(或E(H))到顏色集的一個映射φ:E(G)→{1,2,3,…,k}(或E(H)). 上述稱為圖G(或超圖H)的k種顏色的邊染色, 簡記為k-邊染色. 本文主要討論2-邊染色, 一般用紅色和藍(lán)色來敘述.

2013年, Gyárfás和Sárk?zy[7]提出了一個關(guān)于完全的3-一致超圖的單色劃分的問題.

2018年,Bustamante, Hán和Stein證得下面的引理1.

值得注意的是對于放松圈(loose cycle)上述結(jié)論同樣成立. 另外，引理1中ηn可以被改進(jìn).

目前對于完全超圖的邊染色的單色劃分的研究結(jié)果相對較少, 對于完全的k-部k-一致超圖的邊染色的單色劃分問題還沒有相關(guān)的結(jié)果, 完全的k-部k-一致超圖相對于完全超圖研究起來更復(fù)雜, 對邊的要求更苛刻. 本文研究均衡的完全3-部3-一致超圖的單色放松路的劃分, 為以后研究一般的k-部k-一致超圖的單色劃分問題打下基礎(chǔ).

2 結(jié)論及其證明

證s≤2時，結(jié)論顯然成立. 下面討論s≥3的情況. 在以下證明中，頂點(diǎn)的下標(biāo)是指該點(diǎn)所屬的超圖的部，比如意味著w2∈V2.

證因?yàn)閨W|≥s+1,PR和PB最多能夠覆蓋2s-1個點(diǎn). 考慮兩種情況.

性質(zhì)2PR和PB都是正常的放松路.

2) |V(PR)|=2t+1，其中整數(shù)t≥2, 即PR包含至少2條超邊.PR為{v1,v2,v3}中的某個點(diǎn), 注意V(PB)={u2,u3}，令集合V=ev={vi,vj}(其中i≠j,i,j∈{1,2,3}).由情形1)知超邊viwjwk,vjwiwk(其中i,j,k∈{1,2,3},i≠j≠k)為染藍(lán)色，則PR′=PRe和PB′={viwjwk}∪{wkwivj}與假設(shè)矛盾，故綜上所述得放松路PB是正常的.

此時可知兩條放松路PR,PB均為正常的路, 且很容易得其中放松路PR至少有2條超邊，否則PR={v1,v2,v3}且PB={u1,u2,u3}，類似性質(zhì)2中的情形1)知超邊viwjwk(其中i,j,k∈{1,2,3},i≠j≠k)為染藍(lán)色，超邊uiwjwk(其中i,j,k∈{1,2,3},i≠j≠k)為染紅色. 由對稱性不妨設(shè)u2v3w1為紅色，則PR′=PR∪{v3u2w1}∪{w1u3w2}∪{w2u1w3}與假設(shè)|V(PR)|+|V(PB)|是最大矛盾. 下面我們令放松路PR的第一條超邊為f={x1,x2,x3}, 最后一條超邊為e={v1,v2,v3}; 令放松路PB的最后一條超邊為g={u1,u2,u3}. 對于超邊f(xié),e,g中的二度點(diǎn)分別為x,v,u它們分別是{x1,x2,x3}, {v1,v2,v3}, {u1,u2,u3}中的某個點(diǎn), 令集合X=fx,V=ev,U=gu分別表示超邊f(xié),e,g中去掉二度點(diǎn)以外的點(diǎn)的集合; 取W′?W, 且W′={w1,w2,w3}. 其中X,V是對稱的，從而對于X,V,U的所有可能的隨機(jī)組合，我們可以分為兩種情形進(jìn)行具體討論.

情形1：存在超邊e″={xi,vj,uk}, 其中xi∈X,vj∈V,uk∈U，且i,j,k∈{1,2,3},i≠j≠k.

由超邊e″={xi,vj,uk}知Xxi=xj或xk，Vvj=vi或vk，Uuk=ui或uj，這里我們只證明其中一種，其他可類似得證. 考慮Xxi=xj，Vvj=vi，Uuk=ui，由已知超邊viwjwk，vjwiwk為藍(lán)色，超邊uiwjwk，ukwiwj為紅色. 下面討論超邊e″，如果超邊e″為染紅色, 則PR′=PRf∪e″∪{ukwiwj}∪{wjuiwk}和PB′=PBg(當(dāng)放松路PB恰有一條邊時，PB′={vi,uj})與假設(shè)|V(PR)|+|V(PB)|是最大矛盾. 如果超邊e″為染藍(lán)色, 則新的放松路PR′=PR{f,e}(當(dāng)放松路PR恰有兩條超邊時，PR′={xj,vk})和PB′=PB∪e″∪{vjwiwk}∪{wkwjvi}與假設(shè)|V(PR)|+|V(PB)|是最大矛盾.

情形2：不存在超邊e″={xi,vj,uk}, 其中xi∈X,vj∈V,uk∈U，且i,j,k∈{1,2,3},i≠j≠k.

3 可進(jìn)一步研究的問題

我們討論了關(guān)于均衡的完全3-部3-一致超圖的任意2-邊染色的單色放松路的劃分問題, 那么有沒有其他的工具使關(guān)于均衡的完全3-部3-一致超圖的單色劃分問題得到更好的結(jié)果? 對于均衡的完全k-部k-一致超圖的任意r-邊染色的單色劃分問題呢? 因此, 我們有以下兩個可以進(jìn)一步研究的問題.

問題2對于均衡的完全3-部3-一致超圖的任意的2-邊染色, 至少存在多少條點(diǎn)不交的單色放松路能夠?qū)⒃摮瑘D的所有點(diǎn)全部覆蓋?

問題3對于均衡的完全k-部k-一致超圖的任意的r-邊染色(r≥2),存在多少個點(diǎn)不交的單色放松路或單色放松圈能夠?qū)⒃摮瑘D的所有點(diǎn)全部覆蓋?