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

摘要：

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

关键词：3-正则图、图的边分解、Hamilton图、Hypohamilton图

所属期刊栏目：41

分类号：O157(代数、数论、组合理论)

资助基金：中央高校基本科研业务费专项基金项目NZ2015106.

在线出版日期：2016-11-18（万方平台首次上网日期，不代表论文的发表时间）

页码：134-137