一类3-正则射影平面图的3-分解问题-《集美大学学报（自然科学版）》

文章信息/Info

Author(s):: WANG Yixin; LIU Wenzhong; (School of Mathematics,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China)

Keywords:: decompositions of graphs; projectiveplanar graph; 3-decomposition conjecture

摘要:: 3-分解猜想表明：每一个连通的3-正则图都能分解成一个生成树、一个圈集和一个匹配。设图G是一个连通3-正则射影平面图。从G中删除所有不可分离圈和割边，并压缩产生的所有2-度点，所得到的图是由多个2-连通分支组成的3-正则图，其中最多存在一个非平面分支。当所得的图不存在非平面分支时，本文证明3-分解猜想对图G成立;当所得的图存在一个非平面分支时，本文证明，若该分支的最小欧拉亏格嵌入包含2-面圈，3-面圈或4-面圈，则3-分解猜想对图G成立。

Abstract:: The 3-decomposition conjecture states that every connected cubic graph can be decomposed into a spanning tree,a family of cycles and a matching.Let G be a connected cubic graph on the projective plane.We remove all non-separating cycles and cut-edges from G and suppress all resulting degree-two vertices.Then we obtain a cubic graph consisting of 2-connected components in which there is at most one non-planar component.If the resulting graph does not have a non-planar component,then the 3-Decomposition Conjecture holds for G.Otherwise,the resulting graph has only one non-planar component.We prove that if the minimal Euler genus embedding of the non-planar component φG’ has a 2-facial cycle,a 3-facial cycle,or a 4-facial cycle,the conjecture is true for G.