游华峥

(南京航空航天大学 理学院,南京 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-正则图……