图的哈密尔顿连通性及支撑树特征研究
发布时间：2018-08-17 15:34
【摘要】：图的哈密尔顿性是结构图论的一个重要而且意义深远的研究课题.该问题的产生和发展与著名的四色猜想的研究密切相关,因而备受国内外众多图论专家和学者的关注.图的哈密尔顿路的问题与结构图论中哈密尔顿性的研究也是密切相关的.从算法复杂性来讲,判定一个图是否存在一条哈密尔顿路是NP-完全的.因此,对哈密尔顿路的问题的研究主要集中在给出图中存在哈密尔顿路的充分条件.关于一个图为哈密尔顿连通图的充分条件主要包含以下两类：一类是从参数的角度刻画,常用的有独立数,度和,最小度,邻域并等；另一类是从结构图论的角度,考虑禁用某些特定的子图.设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的支撑树.目前,关于图中是否存在上述三类支撑树问题的研究,主要利用的参数包括：独立数,坚韧度,度和,最小度,邻域并等.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是一个非负整数,G是连通无爪图.若p(G)≤2k+2,则G中存在至多k个分枝点的支撑树.在第三章中,我们证明了：设k和r都是整数,其中k≥2和r≥4,G是2-连通K1,r-free图.若α(G) ≤ k + [k+1/r-3] -[1/|r-k-3|+1],则G中存在至多k个叶子点的支撑树,并且该结论中独立数的上界是最好可能的.由此我们得到如下推论：设k是一个非负整数,G是2-连通K1,4-free图.若a(G)≤2k+5,则G中存在至多k个分枝点的支撑树.此外,我们给出了如下定理：设k是一个非负整数,G是连通K1,4-free图.若a(G)≤2k+5,则图G中存在至多k个分枝点的支撑树或者图G中含有一个块B使得a(B)≤2.最后,我们提出了如下猜想：设k是一个整数,其中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
本文链接：https://www.wllwen.com/kejilunwen/yysx/2188087.html
