二部图中圈结构与路结构研究

发布时间：2021-09-07 13:22

　　路和圈是结构图论的重要研究课题之一,对其进行研究不但有重要的理论意义,而且在计算机科学、信息科学和生物科学中有广泛的应用.确定一个图是否为哈密尔顿图是NP-困难的.由于其和四色定理的密切联系,以及较强的应用性,图的哈密尔顿性一直是图论研究的中心问题之一.本论文主要研究二部图中的圈结构和路结构.全文共分四章,主要内容如下:在本文第一章,首先介绍了文中出现的一些基本定义与符号.接着阐述了研究背景、研究意义以及国内外的研究现状.通过对研究背景和研究现状的讨论,说明了本文主要研究工作的必要性和创新性.在本文第二章,我们主要研究二部图的偶泛圈性与双泛连通性.1975年,Alavi和Williamson首先提出了泛连通的概念.两年后,Williamson证明了任意最小度δ（G）≥ n/2+1的n阶图G是泛连通图.1989年,田丰老师和臧文安老师证明了对任意的x∈Vi,i∈{1,2},满足d（x）>|V3-i|/2+1的二部图G=（V1,V2,E）是奇偶泛连通图.2018年,Du等人证明了任何满足最小度δ（G）≥n/2+1的二部图G=（V1,V2,E）是偶泛连通图,其中n=max{|V1|,|... 

【文章来源】：华中师范大学湖北省 211工程院校 教育部直属院校

【文章页数】：73 页

【学位级别】：博士

【部分图文】：

图１：图Ｇ２ｎ，４，其中几２?３?．??长度为ｍ的圈称作ｍ－圈，也可记为（＾．图Ｇ中最长的圈称为周长，最短的??圈称为围长，分别记作ｃ（Ｇ）和．图的哈密尔顿圈是指过图中所有顶点恰好??

图２：?Ｇ３８中的图．??

图３：?Ｇ中包含Ｚ２ａ“?ａ９ａ《＿２和之１而＿４中至多一个，其中１６?Ｓ?ｉ乞２ｆｃ．??

【参考文献】：
期刊论文
[1]EDGE CONDITION FOR A HAMILTONIAN BIPARTITE GRAPH TO BE BIPANCYCLIC[J]. HU Zhiquan(Faculty of Mathematics and Statistics, Central China Normal University, Wuhan 430079; Institute ofSystems Science, Academy of Mathematics and Systems Sciences,Chinese Academy of Sciences, Beijing 100080, China).  Journal of Systems Science and Complexity. 2003(04)
[2]二部图是哈密顿的一个充分条件[J]. 马美杰,董俊超.  烟台大学学报(自然科学与工程版). 1999(04)
[3]BIPANCYCLISM IN HAMILTONIAN BIPARTITE GRAPHS[J]. 田丰,臧文安.  Systems Science and Mathematical Sciences. 1989(01)
[4]SOME NOTES ON HAMILTONIAN GRAPHS[J]. 施容华.  Science Bulletin. 1987(14)



本文编号：3389623