王丹丹

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

1 介紹

本文考慮的圖都是有限圖，它可以含有平行邊，但不含自環(huán)．對于一個圖G，用V(G)和E(G)分別表示圖G的點集和邊集．用L(G)表示圖G的線圖，其中：L(G)中的兩個點連m(m≤2)條邊當且僅當G中對應的邊有m個公共端點．文中沒有定義的概念和術(shù)語參見文獻[1]．

我們知道，一個連通圖是偶圈可分解的必要條件是它是歐拉圖而且有偶數(shù)條邊，反之是不成立的，例如：K5是一個有10條邊的4-連通4-正則圖，它是歐拉圖但沒有偶圈分解．在1981年Seymour[2]證明了每個2-連通歐拉平面圖是偶圈可分解的；在1994年Zhang[3]證明了2-連通K5-minor-free歐拉圖是偶圈可分解的．在2017年，Huynh在文獻[4]中提出強偶圈分解的概念：如果一個圖的任何一個具有偶數(shù)條邊的細分，都有一個偶圈分解，則稱該圖是強偶圈分解的．根據(jù)強偶圈分解的概念很容易證明Seymour和Zhang的結(jié)果也是強偶圈分解的．Huynh[4]還證明了完全二部圖Km，n(m，n都是偶數(shù))是強偶圈可分解的，進一步推出幾種特殊圖是強偶圈分解的．

Ash和Jackson[5]猜想：每個圈4-邊-連通立方圖有一個控制圈．文獻[6]中已證明：每一個有控制圈的2-連通立方圖線圖是強偶圈分解的．若這個Ash和Jackson猜想正確，則表明每個圈4-邊-連通的立方圖的線圖是強偶圈分解的．本文推廣了文獻[6]中結(jié)果，證明：對2-連通立方圖G，它存在一個圈C使得G-V(C)是一個森林，則L(G)是強偶圈分解的．

下面，我們列舉本文中經(jīng)常會用到一些定義、引理及定理．

一個符號圖(G，Σ)就是由圖G和一個符號集Σ?E(G)組成的圖，其中符號集Σ中的邊稱為符號邊，不在符號集Σ的邊稱為非符號邊．在符號圖中，若一個圈有奇數(shù)條符號邊，則這個圈稱為奇符號圈，否則稱為偶符號圈．

對X?V(G)，δG(X)是無自環(huán)的邊集且每條邊有且僅有一端在X中，則稱δG(X)是X的導出割．若兩個符號集Σ1，Σ2?E(G)的對稱差Δ是一個割，則稱Σ1，Σ2是等價的．注意：符號等價是一種等價關(guān)系．若Σ1，Σ2?E(G)是等價符號，則符號圖(G，Σ1)和(G，Σ2)具有完全相同的偶圈集．因此，如果Σ1和Σ2是等價的，則符號圖(G，Σ1)是偶圈分解的當且僅當符號圖(G，Σ2)是偶圈分解的．

定義1[4]一個圖G是強偶圈分解的當且僅當對E(G)中任意符號集Σ，當|Σ|為偶數(shù)時，則對應的符號圖(G，Σ)是強偶圈分解的．

定義2[6]鏈H是由首尾相連的一串2-圈{c1，c2，…，cn}組成的，其中任意相鄰2-圈ci與ci+1只有一個交點，1≤i≤n-1，如圖1所示．

圖1鏈

定義3[6]次鏈是從鏈H任意選擇一條邊細分一次．

定義4[6]若H是任意哈密頓立方圖，C是H中哈密頓圈．設(shè)H中的點集標為x1，…，xn，y1，…，yn(n≥1)，且C的所有弦集為{x1y1，x2y2，…，xnyn}．對每個i=1，2，…，n，用鏈Hi代替xi與yi之間弦xiyi(Hi的邊是任意大)，產(chǎn)生的4-正則圖稱為鏈弦圖，記為G，如圖2所示．

定義5[6]若H是任意哈密頓立方圖，C是H中哈密頓圈．設(shè)H的點集標為x1，…，xn，y1，…，yn(n≥1)，且C的所有弦集為{x1y1，x2y2，…，xnyn}．令C*表示將C恰好細分一次，將弦x1y1替換為x1和y1之間次鏈H1，并將C*中唯一2度點和H1中唯一2度點結(jié)合記為點z．進一步，用鏈Hi代替xi與yi之間弦xiyi(i=2，…，n)(Hi的邊是任意大)，產(chǎn)生的4-正則圖稱為次鏈弦圖，記為G，如圖3所示．

圖3 次鏈弦圖

下面一些引理將貫穿整個證明過程．

引理1[7]設(shè)(G，Σ)是一個符號圖，對任意不含圈的邊集F?E(G)，存在一個符號ΣF與Σ等價，使得ΣF∩F=?.

引理2[2]每個2-連通歐拉平面圖是強偶圈分解的．

引理3[6]每個鏈弦圖是強偶圈分解的．

引理4[6]每個次鏈弦圖是強偶圈分解的．

定理1[6]若圖G是哈密頓立方圖，則L(G)是強偶圈分解的．

2 立方圖線圖的偶圈分解

在證明主要結(jié)論之前，先證明兩類特殊的4-正則圖是強偶圈分解的．

若G1是任意鏈弦圖，{x0y0，x1y1，x2y2，…，xpyp}為G1的鏈集，C為鏈弦圖的外圈，令C*表示將C細分n次，用鏈xy代替G1中鏈x0y0，其中鏈xy是由m個2-圈組成的，任意選擇其中n(2≤n≤m)個2-圈，將這n個2-圈各選擇一條邊細分一次，并將C*中n個2度點與鏈xy的n個2度點一一結(jié)合，記為點vi．進一步，規(guī)定從x到y(tǒng)的順時針方向依次記為v1，v2，…，vk，…，vn，與之對應的三角形記為D1，D2，…，Dk，…，Dn，產(chǎn)生的4-正則圖稱為廣義次鏈弦圖，記為G，如圖4所示．

圖4 廣義次鏈弦圖

定理2每個廣義次鏈弦圖是強偶圈分解的．

證明設(shè)圖G是以上描述的廣義次鏈弦圖，設(shè)Σ?E(G)是任意一個符號且|Σ|為偶數(shù)，要證明G是強偶圈分解的，只需要證明(G，Σ)是偶圈分解的．

將三角形Di與vi關(guān)聯(lián)的邊分別記為ei1，ei2，Di第三條邊記為ei3．如果D1，D2，…，Dk，…，Dn中至少有一個奇符號三角形，不失一般性，不妨令第一個奇符號三角形為Dk．如果Dk不存在，說明D1，D2，…，Dk，…，Dn均為偶符號三角形．

首先，對每個i≠k，用v′i，v″i替換Di中vi，使得v′i∩C≠?，v″i∩C=?，且保證替換后得到的圖與原圖的對應邊符號保持一致，由于替換后的圖會出現(xiàn)2度點，進一步，收縮圖中所有2度點，得到圖G′，如圖5所示．通過上述操作可以知道G′為次鏈弦圖．需要注意的是：當Dk不存在時，則G′為鏈弦圖，因此由引理3或引理4可知，G′是強偶圈分解的．

圖5 圖G中用v′i，v″i替換Di中vi后并收縮2-點

對每個i≠k，如果v′i，v″i同時含在C1(或C2)上，那么在C1(或C2)中會出現(xiàn)4度點，令滿足上述條件的點集為V，集合V中點vi關(guān)聯(lián)三角形Di的集合記為T．此時作C1、C2與T的對稱差，記C1ΔT=C′1，C2ΔT=C′2．

情況1當C′1，C′2為偶符號圈時，由于已經(jīng)通過對稱差將圈中所有形成閉路的4度點轉(zhuǎn)化為2度點，因此，圖G的偶符號圈集為{C′1，C′2，C3，…，Cs}．

圖6 點x與Dk之間偶符號2-圈及偶符號三角形獨自偶圈分解后剩余圖

通過以上討論可推出G是強偶圈分解的，結(jié)論成立．[8]

若G1是任意鏈弦圖，{x0y0，x′1y′1，x′2y′2，…，x′ny′n}為G1的鏈集，C為鏈弦圖的外圈，令C*表示將C細分i次，用鏈xy代替圖G1中鏈x0y0，其中鏈xy中每個2-圈均選擇其中的一條邊細分一次，且將鏈x′iy′i(i=1，…，j，j≤n)用次鏈xiyi替換，并將鏈xy中i個2度點與C*中2度點一一結(jié)合，記為點qi，鏈xy中剩下2度點分別與鏈xiyi中2度點一一結(jié)合，記為點vi，得到的4-正則圖稱為泛次鏈弦圖，記為G，如圖7所示．

圖7 泛次鏈弦圖

定理3每個泛次鏈弦圖是強偶圈分解的．

證明設(shè)圖G是以上描述的泛次鏈弦圖，設(shè)Σ?E(G)是任意一個符號且|Σ|為偶數(shù)，要證明G是強偶圈分解的，只需要證明(G，Σ)是偶圈分解的．

圖8 只含鏈xy

圖9 含鏈xy和鏈xiyi，i=1，2，…，t2(t2≤n)

情況1當|P1|+|Q1|為偶數(shù)時，只需要令

圖10 第一個vj關(guān)聯(lián)三角形符號為奇第一個三角形Ti符號為奇

因此可推出圖G是強偶圈分解的，結(jié)論成立．

定理4對2-連通立方圖G，如果它存在一個圈C使得G-V(C)是一個森林，則L(G)是強偶圈分解的．

證明在(L(G)，Σ)中|Σ|為偶數(shù)．首先找出圖G的外圈C，那么外圈C的線圖將會形成兩個圈分別記為C1、C2，接下來考慮G-V(C)的線圖，在G-V(C)中任意選擇兩端點均在外圈C的路P1，將它的線圖L(P1)與C1結(jié)合，進一步，將兩個端點均在外圈C的路P2，其中L(P2)與L(P1)是相鄰的，將L(P2)與C2結(jié)合，緊接著，將兩個端點均在外圈C的路P3，其中L(P3)與L(P2)是相鄰的，將L(P3)與C1結(jié)合.以此類推，交替結(jié)合，直到最后一條路Pn的線圖L(Pn)，這樣L(G)將由兩部分組成，如圖11所示的粗實線和粗虛線．

圖11 圖G的線圖分解成兩個子圖

因此L(G)是強偶圈分解的，結(jié)論成立．