游華崢

(南京航空航天大學(xué) 理學(xué)院,南京 211106)

本文中所有的圖均為無(wú)向、簡(jiǎn)單、有限圖.

一個(gè)圖G是一個(gè)二元序?qū)=(V(G)，E(G))，其中V(G)是頂點(diǎn)集，E(G)是邊集且滿足E(G)?V(G)2.若圖G中任意兩個(gè)頂點(diǎn)之間都有兩條獨(dú)立路相連，則稱G為2-連通圖.若G的所有頂點(diǎn)的度均為3，則稱其為立方圖.圖G的線圖L(G)為如此一個(gè)圖：以E(G)為頂點(diǎn)集，且滿足L(G)中任意兩點(diǎn)x,y∈E(G)相鄰當(dāng)且僅當(dāng)x,y在G中相鄰.G的覆蓋是指劃分G成一系列子圖，它們的并集為G.G雙覆蓋是G一個(gè)覆蓋，它使得G的每條邊恰好出現(xiàn)在兩個(gè)子圖里.G的雙圈覆蓋是由一系列圈構(gòu)成的雙覆蓋.一個(gè)圖如果有偶圈的雙覆蓋，則它的線圖有偶圈分解.我們把圈的長(zhǎng)度為偶數(shù)的圈稱之為偶圈.

圖的分解問題是結(jié)構(gòu)圖論中的典型問題.如何把一個(gè)圖的邊集分解成路、圈、樹以及其他特殊的結(jié)構(gòu)一直是圖論中的熱點(diǎn)問題.在這個(gè)方面，一個(gè)很經(jīng)典的定理是：一個(gè)圖有一個(gè)圈分解當(dāng)且僅當(dāng)它是歐拉圖.如果我們?cè)谌Ψ纸獾幕A(chǔ)上加一些限制，問題就會(huì)變得復(fù)雜很多.一個(gè)最簡(jiǎn)單的限制就是要求分解出的每個(gè)圈都是偶圈，我們把這類問題叫做偶圈分解.

定理1 若G是一個(gè)奇度為2的2-連通立方圖，那么L(G)必有一個(gè)偶圈分解.

偶圈分解問題不僅具有自身的意義，還與圖論中一個(gè)經(jīng)典的猜想——圈的雙覆蓋猜想密切相關(guān).因?yàn)槿Φ碾p覆蓋猜想最終歸結(jié)為2-連通的立方圖是否成立.

1 圈的雙覆蓋

與一般的4-正則圖不同，立方圖的線圖是一類有著很好的結(jié)構(gòu)性質(zhì)的4-正則圖.而且它與立方圖的圈覆蓋有著很密切的關(guān)系[7]，除此之外，還與Thomassen猜想[8]每一個(gè)4-連通線圖都是哈密爾頓圖有著一定的聯(lián)系.

本文用到的相關(guān)定理、引理如下：

引理1 3-邊可染的立方圖有偶圈雙覆蓋.

引理2 若立方圖G有一個(gè)偶圈雙覆蓋，則L(G)必有一個(gè)偶圈分解.

定理2 若G是3-邊可染的立方圖，則L(G)有一個(gè)偶圈分解.

關(guān)于立方圖的線圖的偶圈分解，Klas Markstr?m提出如下一個(gè)猜想：

猜想1 若G是一個(gè)2-連通立方圖，則L(G)有一個(gè)偶圈分解.

顯然，猜想1對(duì)于3-邊可染的2-連通立方圖成立.為了方便衡量一個(gè)圖是否3-邊可染，我們定義奇度.

定義1 2-連通立方圖G的2-因子里奇圈的最小數(shù)目K定義為G的奇度，記為o(G)=K.

Klas Markstr?m證明對(duì)于2-連通奇度為2且含有無(wú)弦2-因子的立方圖，猜想1成立，即部分證明了下面定理3.我們證明2-因子有弦的情況該猜想也成立，從而完成定理3的證明.

2 立方圖線圖的偶圈分解

定理3 若G是一個(gè)奇度為2的2-連通立方圖，那么L(G)必有一個(gè)偶圈分解.

證明令C*=(C1，C2,…，Ck)為G的2-因子，其中C1，C2為兩個(gè)奇圈.由于G是2-連通的，故可以找到兩條點(diǎn)不交的路P1，P2，每條路都恰好有一個(gè)點(diǎn)在C1上，一個(gè)點(diǎn)在C2上.我們同時(shí)也可以假設(shè)P1，P2的選擇可以使得每條路和G的2-因子的交集仍然是路，由于圈是連通的這總是可能的.令A(yù)1，A2是C1中連接P1中端點(diǎn)及P2中端點(diǎn)的兩條邊不交的路，由于C1是奇圈，故A1，A2必一個(gè)長(zhǎng)度為奇數(shù)一個(gè)長(zhǎng)度為偶數(shù)，我們假設(shè)A1長(zhǎng)度為奇數(shù).令p1是由A1和P1及P2的第一條邊形成的路，而p2表示由A2和P1及P2的第一條邊形成的路.易知p1長(zhǎng)度為奇，p2長(zhǎng)度為偶，奇偶相異.

現(xiàn)在我們用p1，p2，通過(guò)路和圈來(lái)構(gòu)造覆蓋，使得對(duì)于e∈(P1∪P2)/C*覆蓋兩次，而P1，P2走過(guò)的2-因子中的邊覆蓋一次.我們適當(dāng)?shù)財(cái)U(kuò)大p1，p2來(lái)構(gòu)造這樣的覆蓋，假設(shè)兩條路均從左到右走向C2.

若P1，P2中只有一條路與Ci相交(3≤i≤k)，則p1，p2的走法見圖1.

若P1，P2均與Ci相交(3≤i≤k),則p1，p2的走法見圖2，圖3.

由于Ci(3≤i≤k)均為偶圈，故圖1、圖3的情況下擴(kuò)大后的p1，p2仍奇偶相異.

在圖2的情況下，走過(guò)來(lái)的p1，p2到Ci(3≤i≤k)時(shí)必定有一個(gè)要閉合成圈.如果Ci上左邊的從u到v的路長(zhǎng)是奇數(shù)，我們選擇閉合p1，p2中長(zhǎng)度為奇數(shù)的那一條，否則閉合長(zhǎng)度為偶數(shù)的那一條，從而形成一個(gè)偶圈.然后我們從右邊開始一條新路代替閉合的那一條.由于Ci(3≤i≤k)為偶圈，我們這樣操作之后擴(kuò)大后的p1，p2仍奇偶相異.

圖1

圖2

圖3

當(dāng)p1，p2到達(dá)C2時(shí)，我們用C2中連接P1中端點(diǎn)及P2中端點(diǎn)的兩條邊不交的路B1，B2去形成圈.由于C2長(zhǎng)度為奇數(shù)，故這兩條路B1，B2必奇偶相異，加之p1，p2奇偶互異，這樣即保證了形成的圈均為偶圈，記為D0.

情況1 當(dāng)2-因子中均無(wú)弦存在時(shí)，給定G中一個(gè)圈C，在L(G)中會(huì)有兩個(gè)圈與C關(guān)聯(lián),記作C′,C″.C′中的點(diǎn)是C上的邊；C″中的點(diǎn)是C上及與C上的邊相鄰的邊.C″的長(zhǎng)度是C′的2倍.見圖4.

當(dāng)2-因子中的圈均無(wú)弦存在時(shí)，我們會(huì)得到一個(gè)圈分解D1，它由這些圈的關(guān)聯(lián)圈組成.當(dāng)然，C1′,C2′是奇圈.現(xiàn)在我們從D1中去掉Ci′形成D2.對(duì)于任一e∈(P1∪P2)/C*，我們用C′中的一條邊去替換D2中的C″的兩條邊.由于每一條Pi(P1或P2)會(huì)鄰接兩條或零條圈C上這樣的邊，故此操作并沒有改變C″圈長(zhǎng)的奇偶性.對(duì)于所有的2-因子均進(jìn)行上述操作，于是可以得到一個(gè)偶圈的集合D3.

因此，2-連通立方圖線圖的偶圈分解D由D3及所有的C′(C∈D0)組成.

情況2 當(dāng)2-因子中某些圈有弦存在時(shí)，給定G中一個(gè)圈C，在L(G)中仍然有圈與之關(guān)聯(lián)，只不過(guò)此時(shí)C″由多個(gè)圈構(gòu)成，將這些圈的集合記作C″.見圖5.

圖4

圖5

定義公共弦：P1，P2會(huì)將其經(jīng)過(guò)的圈分成偶數(shù)段(兩段或四段)，將這偶數(shù)段按順時(shí)針進(jìn)行標(biāo)號(hào)(1,2或1,2,3,4)，若弦的兩端點(diǎn)所在段奇偶互異，則稱此弦為公共弦.

由上面的討論知，無(wú)弦時(shí)有p1，p2形成的偶圈集合D0存在.找到所有的C′(C∈D0)，在C′上進(jìn)行修改.將G中有公共弦存在的2-因子的集合記作M，無(wú)公共弦存在的2-因子的集合記作N.

任選一個(gè)有公共弦存在的圈Cj,Cj的弦的集合記作Hj.將僅有一個(gè)端點(diǎn)在Cj上的邊的集合記作Lj.當(dāng)p1，p2經(jīng)過(guò)Cj時(shí)，對(duì)于p1，p2在Cj′上對(duì)應(yīng)的兩條路h,g做以下操作：若遇任一e∈Hj，均用Cj″的兩條邊替換Cj′的一條邊(但一條邊e只替換一次,即若某邊e已被替換過(guò)一次，下次經(jīng)過(guò)時(shí)不予替換).若Cj中有奇數(shù)條弦，則除某一公共弦f需替換兩次外(一次在修改h的過(guò)程中，一次在修改g的過(guò)程中)，其他的弦均替換一次；若有偶數(shù)條弦，各弦均只替換一次.由于用Cj″中的偶數(shù)條邊替換了Cj′中的偶數(shù)條邊，故這樣對(duì)h,g修改過(guò)后形成的路h1,g1在奇圈走過(guò)的長(zhǎng)度仍奇偶互異，在偶圈走過(guò)的長(zhǎng)度仍奇偶相同(性質(zhì)與未修改時(shí)相同).此外，當(dāng)Cj中有偶數(shù)條弦存在的時(shí)候，在Cj′中，對(duì)于任一e∈Lj且e?(P1∪P2)/C*，將它在Cj′中所對(duì)應(yīng)的n條邊用Cj″的2n條邊替換，加上任一e′∈Hj在Cj″中對(duì)應(yīng)的邊(h1,g1未使用的Cj″的邊)，得到偶圈E(Cj)；當(dāng)Cj中有奇數(shù)條弦存在的時(shí)候，在Cj′中，對(duì)于任一e∈Lj且e?(P1∪P2)/C*，將它在Cj′中所對(duì)應(yīng)的n條邊用Cj″的2n條邊替換，加上任一e′∈Hj/f在Cj″中對(duì)應(yīng)的邊(h1,g1未使用的Cj″的邊),得到偶圈E(Cj).將M中的任意一個(gè)圈類似上述修改，得到的所有偶圈的集合記作D11.

若P1，P2經(jīng)過(guò)的圈Cm中無(wú)公共弦，此時(shí)對(duì)于p1，p2在Cm′上對(duì)應(yīng)的兩條路不予修改，L(Cm)剩下的部分為二部偶圖(這里的二部偶圖可以這樣理解：Cm被P1，P2分成的偶數(shù)段里標(biāo)號(hào)為偶數(shù)的邊對(duì)應(yīng)的線圖的點(diǎn)標(biāo)記為白點(diǎn)，標(biāo)號(hào)為奇數(shù)的邊對(duì)應(yīng)的線圖的點(diǎn)標(biāo)記為黑點(diǎn)；對(duì)于非公共弦，若其兩端點(diǎn)均位于Cm上標(biāo)號(hào)為偶數(shù)的部分，則標(biāo)記為黑點(diǎn)，否則標(biāo)白點(diǎn)；僅有一個(gè)端點(diǎn)在Cm上的邊記為L(zhǎng)m，屬于Lm但不屬于(P1∪P2)/C*的邊，若它的端點(diǎn)在Cm上標(biāo)號(hào)為偶數(shù)的部分，則標(biāo)記為黑點(diǎn)，否則標(biāo)白點(diǎn))，由二部偶圖的性質(zhì)可知其必可分解成一系列偶圈，N中的所有圈都具有這樣的性質(zhì)，將其分解出的所有偶圈記作D12.

如此在C′(C∈D0)上修改過(guò)后仍會(huì)形成偶圈集合D13.

對(duì)于P1，P2沒有經(jīng)過(guò)的偶圈Cn，無(wú)弦時(shí)已證，可分解成偶圈；有弦時(shí)Cn′為偶圈，Cn″為二部偶圖，可偶圈分解.將其分解出的所有偶圈記為D14.

于是，2-連通立方圖線圖的偶圈分解D由D11，D12，D13及D14組成.

綜上所述，奇度為2的2-連通立方圖G的線圖L(G)有一個(gè)偶圈分解.

[1] SEYMOUR P D.Even circuits in planar graphs[J].Journal of Combinatorial Theory,1981,31(3):327-338.

[2] ZHANG C Q.On even circuit decompositions of eulerian graphs[J].Journal of Graph Theory,1994,18(1):51-57.

[3] BILL JACKSON.On circuit covers,circuit decompositions and Euler tours of graphs[C].Surveys in Combinatorics,1993:191-210.

[4] ROMEO RIZZI.On 4-connected graphs without even cycle decompositions[J].Discrete Math.,2001，234 (1-3):181-186.

[6] MARKSTR?M K.Even cycle decompositions of 4-regular graphs and line graphs[J].Discrete Mathematics,2012,312(17):2676-2681.

[8] THOMASSEN C.Reflections on graph theory[J].Journal of Graph Theory,2010,10(3):309-324.