圖的哈密爾頓連通性及支撐樹特征研究
發(fā)布時(shí)間：2018-08-17 15:34
【摘要】：圖的哈密爾頓性是結(jié)構(gòu)圖論的一個(gè)重要而且意義深遠(yuǎn)的研究課題.該問題的產(chǎn)生和發(fā)展與著名的四色猜想的研究密切相關(guān),因而備受國內(nèi)外眾多圖論專家和學(xué)者的關(guān)注.圖的哈密爾頓路的問題與結(jié)構(gòu)圖論中哈密爾頓性的研究也是密切相關(guān)的.從算法復(fù)雜性來講,判定一個(gè)圖是否存在一條哈密爾頓路是NP-完全的.因此,對(duì)哈密爾頓路的問題的研究主要集中在給出圖中存在哈密爾頓路的充分條件.關(guān)于一個(gè)圖為哈密爾頓連通圖的充分條件主要包含以下兩類：一類是從參數(shù)的角度刻畫,常用的有獨(dú)立數(shù),度和,最小度,鄰域并等；另一類是從結(jié)構(gòu)圖論的角度,考慮禁用某些特定的子圖.設(shè)H是由連通圖所組成的圖類.若對(duì)任意的圖H∈H,圖G都不包含H作為導(dǎo)出子圖,則稱圖G是H-free的并且稱H是圖G的一個(gè)禁用子圖.一個(gè)圖稱為無爪圖如果這個(gè)圖是K1,3-free的.Faudree等人在文獻(xiàn)[J.R. Faudree, R. J. Faudree, Z. Ryjacek and P. Vrana, On forbidden pairs implying Hamiltion-connectedness, J Graph Theory 72 (2012),247-365.]中證明了：對(duì)于X=K1,3并且Y ∈{P8,N1,1,3, N1,2,2},如果G是3-連通{X,Y}-free圖,則圖G是哈密爾頓連通的.在第二章中,我們部分推廣了該結(jié)果,證明了任何3-連通{K1,3,N1,2,3-free圖都是哈密爾頓連通圖.注意到圖G中存在一條哈密爾頓路當(dāng)且僅當(dāng)下述三個(gè)條件之一成立：(i)圖G中存在恰含兩個(gè)葉子點(diǎn)的支撐樹.(ii)圖G中存在含零個(gè)分枝點(diǎn)的支撐樹.(iii)圖G中存在最大度至多為2的支撐樹.因此,下述問題是圖中哈密爾頓路問題的自然推廣.(1)圖G中存在至多k個(gè)葉子點(diǎn)的支撐樹.(2)圖G中存在至多k個(gè)分枝點(diǎn)的支撐樹.(3)圖G中存在最大度至多為k的支撐樹.目前,關(guān)于圖中是否存在上述三類支撐樹問題的研究,主要利用的參數(shù)包括：獨(dú)立數(shù),堅(jiān)韌度,度和,最小度,鄰域并等.Matsuda, Ozeki和Yamashita在文獻(xiàn)[H. Matsuda, K. Ozeki and T. Yamashita, Spanning trees with a bounded number ofbranch vertices in a claw-free graph, Graphs and Combinatorics.30(2014) 429-437.]中證明了：設(shè)k是一個(gè)非負(fù)整數(shù),G是連通無爪圖.若p(G)≤2k+2,則G中存在至多k個(gè)分枝點(diǎn)的支撐樹.在第三章中,我們證明了：設(shè)k和r都是整數(shù),其中k≥2和r≥4,G是2-連通K1,r-free圖.若α(G) ≤ k + [k+1/r-3] -[1/|r-k-3|+1],則G中存在至多k個(gè)葉子點(diǎn)的支撐樹,并且該結(jié)論中獨(dú)立數(shù)的上界是最好可能的.由此我們得到如下推論：設(shè)k是一個(gè)非負(fù)整數(shù),G是2-連通K1,4-free圖.若a(G)≤2k+5,則G中存在至多k個(gè)分枝點(diǎn)的支撐樹.此外,我們給出了如下定理：設(shè)k是一個(gè)非負(fù)整數(shù),G是連通K1,4-free圖.若a(G)≤2k+5,則圖G中存在至多k個(gè)分枝點(diǎn)的支撐樹或者圖G中含有一個(gè)塊B使得a(B)≤2.最后,我們提出了如下猜想：設(shè)k是一個(gè)整數(shù),其中k≥2,G是2-連通無爪圖.若a(G)≤2k+2,則G中存在至多k個(gè)葉子點(diǎn)的支撐樹.
[Abstract]:The Hamiltonian property of graphs is an important and far-reaching research topic in structural graph theory. The emergence and development of this problem is closely related to the study of the famous four-color conjecture, which attracts the attention of many graph experts and scholars at home and abroad. The problem of Hamiltonian path of graphs and the study of Hamiltonian property in structural graph theory are also closely related. In terms of algorithm complexity, it is NP-complete to determine whether a graph has a Hamiltonian path. Therefore, the study of Hamiltonian paths mainly focuses on the sufficient conditions for the existence of Hamiltonian paths in a graph. From the point of view of the parameter, we often use the independent number, degree, minimum degree, neighborhood Union and so on; the other is from the point of view of structured graph theory, we consider disabling certain subgraphs. Let H be a graph class composed of connected graphs. A graph is called a claw-free graph if it is K1,3-free. Faudree et al. proved in the literature [J.R.Faudree, R.J.Faudree, Z.Ryjacek and P.Vrana, On forbidden pairs implying Hamiltion-connectedness, J Graph Theory 72 (2012), 247-365.]: for X = K1,3 and Y <{P8, N1, 1, N1, 2, 2}, if G is 3-P8, N1, N1, 2}. In Chapter 2, we generalize the result partially and prove that any 3-connected {K1, 3, N1, 2, 3-free graph is a Hamiltonian connected graph. We note that there is a Hamiltonian path in graph G if and only if one of the following three conditions holds: (i) there are two leaf subpoints in graph G (ii) there is a spanning tree with zero branches in graph G. (iii) there is a spanning tree with a maximum of 2 in graph G. Therefore, the following problem is a natural extension of the Hamiltonian path problem in graph G. (1) there is a spanning tree with up to K leaf points in graph G. (2) there is a spanning tree with up to K branches in graph G. (3) there is a spanning tree with a maximum of up to 2 branches in graph G. Most of them are k-spanning trees. At present, the main parameters used to study the existence of these three kinds of spanning trees include: independence number, toughness, degree, minimum degree, neighborhood Union and so on. Matsuda, Ozeki and Yamashita in the literature [H. Matsuda, K. Ozeki and T. Yamashita, Spanning trees with a bounded number of branches of vertices I. Let K be a nonnegative integer and G be a connected claw-free graph. If P (G) < 2K + 2, then G has a spanning tree of up to K branches. In Chapter 3, we prove that let K and R be integers, where k < 2 and R < 4, G is a 2-connected K1, r-free graph. In addition, we give the following corollaries: let K be a non-negative integer and G be a 2-connected K1,4-free graph. If a (G) < 2K + 5, then G has up to K branches. Let K be a nonnegative integer and G be a connected K1,4-free graph. If a (G) <2k+5, then there is a spanning tree with up to K branching points in G or a block B in G so that a (B) <2. Finally, we propose the following conjecture: Let K be an integer, where k <2, G is a 2-connected claw-free graph. The spanning tree of a subdot.
【學(xué)位授予單位】：華中師范大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
本文編號(hào)：2188087
[Abstract]:The Hamiltonian property of graphs is an important and far-reaching research topic in structural graph theory. The emergence and development of this problem is closely related to the study of the famous four-color conjecture, which attracts the attention of many graph experts and scholars at home and abroad. The problem of Hamiltonian path of graphs and the study of Hamiltonian property in structural graph theory are also closely related. In terms of algorithm complexity, it is NP-complete to determine whether a graph has a Hamiltonian path. Therefore, the study of Hamiltonian paths mainly focuses on the sufficient conditions for the existence of Hamiltonian paths in a graph. From the point of view of the parameter, we often use the independent number, degree, minimum degree, neighborhood Union and so on; the other is from the point of view of structured graph theory, we consider disabling certain subgraphs. Let H be a graph class composed of connected graphs. A graph is called a claw-free graph if it is K1,3-free. Faudree et al. proved in the literature [J.R.Faudree, R.J.Faudree, Z.Ryjacek and P.Vrana, On forbidden pairs implying Hamiltion-connectedness, J Graph Theory 72 (2012), 247-365.]: for X = K1,3 and Y <{P8, N1, 1, N1, 2, 2}, if G is 3-P8, N1, N1, 2}. In Chapter 2, we generalize the result partially and prove that any 3-connected {K1, 3, N1, 2, 3-free graph is a Hamiltonian connected graph. We note that there is a Hamiltonian path in graph G if and only if one of the following three conditions holds: (i) there are two leaf subpoints in graph G (ii) there is a spanning tree with zero branches in graph G. (iii) there is a spanning tree with a maximum of 2 in graph G. Therefore, the following problem is a natural extension of the Hamiltonian path problem in graph G. (1) there is a spanning tree with up to K leaf points in graph G. (2) there is a spanning tree with up to K branches in graph G. (3) there is a spanning tree with a maximum of up to 2 branches in graph G. Most of them are k-spanning trees. At present, the main parameters used to study the existence of these three kinds of spanning trees include: independence number, toughness, degree, minimum degree, neighborhood Union and so on. Matsuda, Ozeki and Yamashita in the literature [H. Matsuda, K. Ozeki and T. Yamashita, Spanning trees with a bounded number of branches of vertices I. Let K be a nonnegative integer and G be a connected claw-free graph. If P (G) < 2K + 2, then G has a spanning tree of up to K branches. In Chapter 3, we prove that let K and R be integers, where k < 2 and R < 4, G is a 2-connected K1, r-free graph. In addition, we give the following corollaries: let K be a non-negative integer and G be a 2-connected K1,4-free graph. If a (G) < 2K + 5, then G has up to K branches. Let K be a nonnegative integer and G be a connected K1,4-free graph. If a (G) <2k+5, then there is a spanning tree with up to K branching points in G or a block B in G so that a (B) <2. Finally, we propose the following conjecture: Let K be an integer, where k <2, G is a 2-connected claw-free graph. The spanning tree of a subdot.
【學(xué)位授予單位】：華中師范大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5
【參考文獻(xiàn)】
相關(guān)期刊論文 前1條
1 LIN HouYuan;HU ZhiQuan;;Every 3-connected {K_(1,3),N_(3,3,3)}-free graph is Hamiltonian[J];Science China(Mathematics);2013年08期
，本文編號(hào)：2188087
本文鏈接：http://sikaile.net/kejilunwen/yysx/2188087.html
最近更新
教材專著
