圖的哈密爾頓連通性及支撐樹特征研究
發(fā)布時間：2018-08-17 15:34
【摘要】：圖的哈密爾頓性是結構圖論的一個重要而且意義深遠的研究課題.該問題的產生和發(fā)展與著名的四色猜想的研究密切相關,因而備受國內外眾多圖論專家和學者的關注.圖的哈密爾頓路的問題與結構圖論中哈密爾頓性的研究也是密切相關的.從算法復雜性來講,判定一個圖是否存在一條哈密爾頓路是NP-完全的.因此,對哈密爾頓路的問題的研究主要集中在給出圖中存在哈密爾頓路的充分條件.關于一個圖為哈密爾頓連通圖的充分條件主要包含以下兩類：一類是從參數(shù)的角度刻畫,常用的有獨立數(shù),度和,最小度,鄰域并等；另一類是從結構圖論的角度,考慮禁用某些特定的子圖.設H是由連通圖所組成的圖類.若對任意的圖H∈H,圖G都不包含H作為導出子圖,則稱圖G是H-free的并且稱H是圖G的一個禁用子圖.一個圖稱為無爪圖如果這個圖是K1,3-free的.Faudree等人在文獻[J.R. Faudree, R. J. Faudree, Z. Ryjacek and P. Vrana, On forbidden pairs implying Hamiltion-connectedness, J Graph Theory 72 (2012),247-365.]中證明了：對于X=K1,3并且Y ∈{P8,N1,1,3, N1,2,2},如果G是3-連通{X,Y}-free圖,則圖G是哈密爾頓連通的.在第二章中,我們部分推廣了該結果,證明了任何3-連通{K1,3,N1,2,3-free圖都是哈密爾頓連通圖.注意到圖G中存在一條哈密爾頓路當且僅當下述三個條件之一成立：(i)圖G中存在恰含兩個葉子點的支撐樹.(ii)圖G中存在含零個分枝點的支撐樹.(iii)圖G中存在最大度至多為2的支撐樹.因此,下述問題是圖中哈密爾頓路問題的自然推廣.(1)圖G中存在至多k個葉子點的支撐樹.(2)圖G中存在至多k個分枝點的支撐樹.(3)圖G中存在最大度至多為k的支撐樹.目前,關于圖中是否存在上述三類支撐樹問題的研究,主要利用的參數(shù)包括：獨立數(shù),堅韌度,度和,最小度,鄰域并等.Matsuda, Ozeki和Yamashita在文獻[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.]中證明了：設k是一個非負整數(shù),G是連通無爪圖.若p(G)≤2k+2,則G中存在至多k個分枝點的支撐樹.在第三章中,我們證明了：設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個葉子點的支撐樹,并且該結論中獨立數(shù)的上界是最好可能的.由此我們得到如下推論：設k是一個非負整數(shù),G是2-連通K1,4-free圖.若a(G)≤2k+5,則G中存在至多k個分枝點的支撐樹.此外,我們給出了如下定理：設k是一個非負整數(shù),G是連通K1,4-free圖.若a(G)≤2k+5,則圖G中存在至多k個分枝點的支撐樹或者圖G中含有一個塊B使得a(B)≤2.最后,我們提出了如下猜想：設k是一個整數(shù),其中k≥2,G是2-連通無爪圖.若a(G)≤2k+2,則G中存在至多k個葉子點的支撐樹.
[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.
【學位授予單位】：華中師范大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：O157.5
本文編號：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.
【學位授予單位】：華中師范大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：O157.5
【參考文獻】
相關期刊論文 前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期
，本文編號：2188087
本文鏈接：http://www.sikaile.net/kejilunwen/yysx/2188087.html
最近更新
教材專著
