含有Hamilton路的三正則圖的分解
發(fā)布時間：2018-08-08 18:34
【摘要】：圖的分解是把圖的邊集分解成邊不交的子集。把三正則圖分解成具有某種性質(zhì)的子圖問題是結(jié)構(gòu)圖論中典型的問題。在2011年,Hoffmann-Ostenhof提出如下猜想:每一個連通三正則圖的邊集均能分解成一個生成樹、匹配和一系列圈。猜想被提出后引起圖論學(xué)者極大關(guān)注。隨后,多篇文獻研究了這個猜想,并得到了部分結(jié)果。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路的三正則圖,這個猜想是成立的。作為我們結(jié)果的特例,可以直接推導(dǎo)出有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.
【學(xué)位授予單位】：南京航空航天大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：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.
【學(xué)位授予單位】：南京航空航天大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157.5
【參考文獻】
相關(guān)期刊論文 前5條
1 李盼盼;劉文忠;;具有長圈的3-正則圖的分解[J];昆明理工大學(xué)學(xué)報(自然科學(xué)版);2016年05期
2 劉彥佩;;我所初識的高等圖論(Ⅰ):在虧格為0曲面上[J];昆明理工大學(xué)學(xué)報(自然科學(xué)版);2016年03期
3 任韓;劉兵兵;;曲面上圖染色的研究綜述(上)[J];昆明理工大學(xué)學(xué)報(自然科學(xué)版);2016年01期
4 申婷茹;劉文忠;;BLANUA SNARK冪的虧格（英文）[J];昆明理工大學(xué)學(xué)報(自然科學(xué)版);2014年04期
5 劉彥佩;;我所認識的拓撲圖論(Ⅰ):球面上十部曲[J];昆明理工大學(xué)學(xué)報(自然科學(xué)版);2013年01期
，本文編號：2172664
本文鏈接：http://sikaile.net/kejilunwen/yysx/2172664.html
最近更新
教材專著
