具有长圈的3-正则图的分解

Decomposition of Cubic Graphs with Long Cycles

在2011年,Hoffmann-Ostenhof提出如下猜想:每一个有n个顶点的3-正则图G的边集能分解成一个生成树、匹配和一系列圈.猜想被提出后引起图论学者极大关注.随后,多篇文献研究了这个猜想,得到了部分结果.其中,对于3-正则3-连通平面图、3-正则3-连通射影平面图以及3-正则Hamilton图等图类,这个猜想被证明是成立的,这些结果已分别发表在图论领域国际权威期刊上.本文证明:围长为(n-1)的3-正则图G的边集能分解成一个生成树、匹配和一系列圈.由我们的结果,可以直接导出3-正则Hamilton图,Hypohamilton图的如此分解.

In 2011,Hoffmann- Ostenhof conjectured that if G is a connected cubic graph with n vertices,then the edge set of G can be decomposed into a spanning tree,a matching and a family of cycles. Many researchers immediately focused on the conjecture. Some literatures investigated it and have got some partial results. For 3-connected cubic plane graphs,3- connected cubic graphs on the projective plane and Hamilton cubic graphs,the conjecture is true,which have been published on some international key journals on graph theory. In this paper,it is proved that if G is a cubic graph with girth（ n- 1）,the conjecture is true,from which the decompositions of the Hamilton cubic graph and Hypohamilton cubic graph are easily deduced.