含有Hamilton路的三正则图的分解
发布时间：2018-08-08 18:34
【摘要】：图的分解是把图的边集分解成边不交的子集。把三正则图分解成具有某种性质的子图问题是结构图论中典型的问题。在2011年,Hoffmann-Ostenhof提出如下猜想:每一个连通三正则图的边集均能分解成一个生成树、匹配和一系列圈。猜想被提出后引起图论学者极大关注。随后,多篇文献研究了这个猜想,并得到了部分结果。Ozaki和Ye[European Journal of Combinatorics.52(2016)40-46]证明这个猜想对于3-连通三正则平面图、射影平面图是成立的。Hoffmann-Ostenhof,Kaiser和Ozaki[Arxiv:1609.05059v1[math.CO]16(2016)]证明这个猜想对三正则平面图成立。文献[1,29]证明三正则Hamiltonian图也满足此猜想。在本文中,我们证明:对于含有Hamilton路的三正则图,这个猜想是成立的。作为我们结果的特例,可以直接推导出有n个点且围长至少为(7)n-1(8)的三正则图也能有上述分解。
[Abstract]:The decomposition of a graph is to decompose the edge set of a graph into a subset of edges disjoint. The decomposition of three regular graphs into subgraph problems with some properties is a typical problem in structural graph theory. In 2011, Hoffmann-Ostenhof proposed the following conjecture: the edge set of every connected triregular graph can be decomposed into a spanning tree, matching and a series of cycles. After the conjecture was put forward, graph theorists paid great attention to it. Then, several literatures have studied this conjecture, and obtained some results. Ozaki and Ye [European Journal of Combinatorics.52 (2016) 40-46] prove that this conjecture holds true for 3-connected triregular planar graphs. Hoffmann-OstenhofKaiser and Ozaki [Arxiv:1609.05059v1 [math.CO] 16 (2016)] prove that this conjecture is true for 3-connected triregular planar graphs. In reference [1], it is proved that three regular Hamiltonian graphs satisfy this conjecture. In this paper, we prove that this conjecture is true for three regular graphs with Hamilton paths. As a special case of our results, we can directly deduce that three regular graphs with n points and at least (7) n-1 (8) girth can also have the above decomposition.
【学位授予单位】：南京航空航天大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
本文编号：2172664
[Abstract]:The decomposition of a graph is to decompose the edge set of a graph into a subset of edges disjoint. The decomposition of three regular graphs into subgraph problems with some properties is a typical problem in structural graph theory. In 2011, Hoffmann-Ostenhof proposed the following conjecture: the edge set of every connected triregular graph can be decomposed into a spanning tree, matching and a series of cycles. After the conjecture was put forward, graph theorists paid great attention to it. Then, several literatures have studied this conjecture, and obtained some results. Ozaki and Ye [European Journal of Combinatorics.52 (2016) 40-46] prove that this conjecture holds true for 3-connected triregular planar graphs. Hoffmann-OstenhofKaiser and Ozaki [Arxiv:1609.05059v1 [math.CO] 16 (2016)] prove that this conjecture is true for 3-connected triregular planar graphs. In reference [1], it is proved that three regular Hamiltonian graphs satisfy this conjecture. In this paper, we prove that this conjecture is true for three regular graphs with Hamilton paths. As a special case of our results, we can directly deduce that three regular graphs with n points and at least (7) n-1 (8) girth can also have the above decomposition.
【学位授予单位】：南京航空航天大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5
【参考文献】
相关期刊论文 前5条
1 李盼盼;刘文忠;;具有长圈的3-正则图的分解[J];昆明理工大学学报(自然科学版);2016年05期
2 刘彦佩;;我所初识的高等图论(Ⅰ):在亏格为0曲面上[J];昆明理工大学学报(自然科学版);2016年03期
3 任韩;刘兵兵;;曲面上图染色的研究综述(上)[J];昆明理工大学学报(自然科学版);2016年01期
4 申婷茹;刘文忠;;BLANUA SNARK幂的亏格（英文）[J];昆明理工大学学报(自然科学版);2014年04期
5 刘彦佩;;我所认识的拓扑图论(Ⅰ):球面上十部曲[J];昆明理工大学学报(自然科学版);2013年01期
，本文编号：2172664
本文链接：https://www.wllwen.com/kejilunwen/yysx/2172664.html
