2-連通奇度為2的立方圖的線圖的偶圈分解

游華崢

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

本文中所有的圖均為無向、簡單、有限圖.

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

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

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

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

1 圈的雙覆蓋

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

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

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

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

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

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

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

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

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

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

2 立方圖線圖的偶圈分解

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

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

現(xiàn)在我們用p1，p2，通過路和圈來構(gòu)造覆蓋，使得對于e∈(P1∪P2)/C*覆蓋兩次，而P1，P2走過的2-因子中的邊覆蓋一次.我們適當?shù)財U大p1，p2來構(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的情況下擴大后的p1，p2仍奇偶相異.

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

圖1

圖2

圖3

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

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

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

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

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

圖4

圖5

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

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

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

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

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

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

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

綜上所述，奇度為2的2-連通立方圖G的線圖L(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.