论文摘要
这篇论文分为两部分,分别介绍了有关图中的哈密顿圈和图的列表线性荫度的一些研究成果。第一部分由三章组成。在第一章引言中,我们给出了图的有关定义及概念并介绍了图的哈密顿圈的研究背景。第二章中我们研究了中间图的补图的哈密顿性。图G的中间图M（G）的顶点集为V （G）∪E（G）,两个点x和y相邻当且仅当x和y中至少有一个是G的一条边,并且它们在G中相邻或关联。我们定义图G的中间图M（G）的补图为M（G）,它的顶点集为V （G）∪E（G）,两个顶点x和y相邻当且仅当下面条件之一成立:（i） x,y∈V （G）, （ii） x,y∈E（G）,并且x和y在G中不相邻, （iii） x和y中的一个在V （G）中,另一个在E（G）中,并且它们在G中不关联。在本文中,我们证明了κ（M（G）） =δ（M（G））,以及G的中间图的补图M（G）是哈密顿图当且仅当G不是星图并且不同构于{K1,2K1,K2,K2∪K1,K3,K3∪K1}中的任何图。第三章中我们研究了2K2-free图的线图的哈密顿性。2K2-free图是指不包含一对独立边作为导出子图的图。Kriesell证明了所有4-连通的无爪图的线图是哈密顿连通的。在本文中,我们证明了如果图G是2K2-free图并且不同构与K2, P3和双星图,那么线图L（G）是哈密顿图。进一步我们应用由Ryja′c?ek引入的闭包的概念,给出了直径不超过2的2-连通无爪图是哈密顿图这个定理的新的证明方法。第二部分包含四章。第四章中,我们引入了图G的列表线性荫度lla（G）的概念,并且提出了一个猜想。一个线性森林是一个每个连通分支均为路的图。图G的线性荫度la（G）是把G的边集划分成线性森林的最小值,这个概念是由Harary提出的。G的边集的一个列表安排L是对G的每一条边e安排一个颜色集合L（e）（?）N,这里N是自然数的集合。如果G有一个着色φ使得对每一条边e有φ（e）∈L（e）并且对每一个i∈Cφ使得图(V （G）,φ-1（i）)是一个线性森林（这里Cφ= {φ（e）|e∈E（G）}）,那么我们称G是线性L-可着色的并且φ是G的一个线性L-着色。如果每一个对所有边e都满足|L（e）| = k的列表安排L使得G是线性L-可着色的,则称G是线性k-列表可着色的。图G的列表线性荫度是使得G是线性k-列表可着色的最小k值,记为lla（G）。显然la（G） lla（G）,因此我们提出下面的猜想:列表线性荫度猜想:对任何简单图G,有在第五章中,我们证明了对于Δ≥13的平面图,或者Δ≥7且不含i-圈（i∈{3,4,5}）的平面图G,列表线性荫度猜想是正确的,即lla（G） = la（G） =（?）并且对于Δ≥9的平面图G有在第六章和第七章中,我们分别证明了Halin图和系列-平行图满足列表线性荫度猜想（有关Halin图和系列-平行图的定义参见6.1节和7.1节）。我们得到了下面的结果。1.设G是一个Halin图,则2.设G是一个系列-平行图。则如果?（G） = 2并且G包含一个圈;2 ,其它情况。