2-连通奇度为2的立方图的线图的偶圈分解

游华峥

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

本文中所有的图均为无向、简单、有限图.

一个图G是一个二元序对G=(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的每条边恰好出现在两个子图里.G的双圈覆盖是由一系列圈构成的双覆盖.一个图如果有偶圈的双覆盖，则它的线图有偶圈分解.我们把圈的长度为偶数的圈称之为偶圈.

图的分解问题是结构图论中的典型问题.如何把一个图的边集分解成路、圈、树以及其他特殊的结构一直是图论中的热点问题.在这个方面，一个很经典的定理是：一个图有一个圈分解当且仅当它是欧拉图.如果我们在圈分解的基础上加一些限制，问题就会变得复杂很多.一个最简单的限制就是要求分解出的每个圈都是偶圈，我们把这类问题叫做偶圈分解.

定理1 若G是一个奇度为2的2-连通立方图，那么L(G)必有一个偶圈分解.

偶圈分解问题不仅具有自身的意义，还与图论中一个经典的猜想——圈的双覆盖猜想密切相关.因为圈的双覆盖猜想最终归结为2-连通的立方图是否成立.

1 圈的双覆盖

与一般的4-正则图不同，立方图的线图是一类有着很好的结构性质的4-正则图.而且它与立方图的圈覆盖有着很密切的关系[7]，除此之外，还与Thomassen猜想[8]每一个4-连通线图都是哈密尔顿图有着一定的联系.

本文用到的相关定理、引理如下：

引理1 3-边可染的立方图有偶圈双覆盖.

引理2 若立方图G有一个偶圈双覆盖，则L(G)必有一个偶圈分解.

定理2 若G是3-边可染的立方图，则L(G)有一个偶圈分解.

关于立方图的线图的偶圈分解，Klas Markström提出如下一个猜想：

猜想1 若G是一个2-连通立方图，则L(G)有一个偶圈分解.

显然，猜想1对于3-边可染的2-连通立方图成立.为了方便衡量一个图是否3-边可染，我们定义奇度.

定义1 2-连通立方图G的2-因子里奇圈的最小数目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上.我们同时也可以假设P1，P2的选择可以使得每条路和G的2-因子的交集仍然是路，由于圈是连通的这总是可能的.令A1，A2是C1中连接P1中端点及P2中端点的两条边不交的路，由于C1是奇圈，故A1，A2必一个长度为奇数一个长度为偶数，我们假设A1长度为奇数.令p1是由A1和P1及P2的第一条边形成的路，而p2表示由A2和P1及P2的第一条边形成的路.易知p1长度为奇，p2长度为偶，奇偶相异.

现在我们用p1，p2，通过路和圈来构造覆盖，使得对于e∈(P1∪P2)/C*覆盖两次，而P1，P2走过的2-因子中的边覆盖一次.我们适当地扩大p1，p2来构造这样的覆盖，假设两条路均从左到右走向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的路长是奇数，我们选择闭合p1，p2中长度为奇数的那一条，否则闭合长度为偶数的那一条，从而形成一个偶圈.然后我们从右边开始一条新路代替闭合的那一条.由于Ci(3≤i≤k)为偶圈，我们这样操作之后扩大后的p1，p2仍奇偶相异.

图1

图2

图3

当p1，p2到达C2时，我们用C2中连接P1中端点及P2中端点的两条边不交的路B1，B2去形成圈.由于C2长度为奇数，故这两条路B1，B2必奇偶相异，加之p1，p2奇偶互异，这样即保证了形成的圈均为偶圈，记为D0.

情况1 当2-因子中均无弦存在时，给定G中一个圈C，在L(G)中会有两个圈与C关联,记作C′,C″.C′中的点是C上的边；C″中的点是C上及与C上的边相邻的边.C″的长度是C′的2倍.见图4.

当2-因子中的圈均无弦存在时，我们会得到一个圈分解D1，它由这些圈的关联圈组成.当然，C1′,C2′是奇圈.现在我们从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)中仍然有圈与之关联，只不过此时C″由多个圈构成，将这些圈的集合记作C″.见图5.

图4

图5

定义公共弦：P1，P2会将其经过的圈分成偶数段(两段或四段)，将这偶数段按顺时针进行标号(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经过Cj时，对于p1，p2在Cj′上对应的两条路h,g做以下操作：若遇任一e∈Hj，均用Cj″的两条边替换Cj′的一条边(但一条边e只替换一次,即若某边e已被替换过一次，下次经过时不予替换).若Cj中有奇数条弦，则除某一公共弦f需替换两次外(一次在修改h的过程中，一次在修改g的过程中)，其他的弦均替换一次；若有偶数条弦，各弦均只替换一次.由于用Cj″中的偶数条边替换了Cj′中的偶数条边，故这样对h,g修改过后形成的路h1,g1在奇圈走过的长度仍奇偶互异，在偶圈走过的长度仍奇偶相同(性质与未修改时相同).此外，当Cj中有偶数条弦存在的时候，在Cj′中，对于任一e∈Lj且e∉(P1∪P2)/C*，将它在Cj′中所对应的n条边用Cj″的2n条边替换，加上任一e′∈Hj在Cj″中对应的边(h1,g1未使用的Cj″的边)，得到偶圈E(Cj)；当Cj中有奇数条弦存在的时候，在Cj′中，对于任一e∈Lj且e∉(P1∪P2)/C*，将它在Cj′中所对应的n条边用Cj″的2n条边替换，加上任一e′∈Hj/f在Cj″中对应的边(h1,g1未使用的Cj″的边),得到偶圈E(Cj).将M中的任意一个圈类似上述修改，得到的所有偶圈的集合记作D11.

若P1，P2经过的圈Cm中无公共弦，此时对于p1，p2在Cm′上对应的两条路不予修改，L(Cm)剩下的部分为二部偶图(这里的二部偶图可以这样理解：Cm被P1，P2分成的偶数段里标号为偶数的边对应的线图的点标记为白点，标号为奇数的边对应的线图的点标记为黑点；对于非公共弦，若其两端点均位于Cm上标号为偶数的部分，则标记为黑点，否则标白点；仅有一个端点在Cm上的边记为Lm，属于Lm但不属于(P1∪P2)/C*的边，若它的端点在Cm上标号为偶数的部分，则标记为黑点，否则标白点)，由二部偶图的性质可知其必可分解成一系列偶圈，N中的所有圈都具有这样的性质，将其分解出的所有偶圈记作D12.

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

对于P1，P2没有经过的偶圈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.