度和与子图结构的研究最早可追溯到1952年,由Dirac在研究著名的Hamil-tonian 问题时提出的.它研究的是在度和比较大的结构里某种子结构的存在性问题.度和与子图结构的研究涉及图论的众多领域诸如Hamiltonian图理论,染色理论,极值图论等.Hamiltonian图理论是推动这一领域迅速发展的重要动力之一.例如,在研究Hamiltonian问题的过程中,不断涌现的新方法和新问题,不但使得Hamiltonian图理论成为图论的主要领域之一,而且推动度和与子图结构的研究领域迅速发展壮大.许多数学家在度和与子图结构领域做出了大量的努力和贡献,包括N.Alon,J.Bondy,P.Erdos,G.Fan,O.Ore等.对于解决该领域的大量问题,结构分析,概率方法等都是强有力的工具.Hamiltonian图理论拥有众多分支,例如,涉及诸多类型圈子结构的Hamil-tonicity理论,包含特殊类型树子结构的traceablity理论等.图的染色理论是图论的传统领域之一,其内容十分丰富,包括经典的边染色,点染色,以及在此基础上添加或放松约束所产生的各种染色问题.图参数的极值问题是极值图论的一个研究方向.本论文研究的度和与子图结构问题,包括Hamiltonian图理论的控制圈的存在性问题和包含有限个分支点的生成树的存在性问题,以及染色理论的广义边染色问题.最后我们研究涉及距离的图参数的极值问题.第1章,我们首先介绍本文涉及到的一些基本概念和符号.其次,对本文涉及问题的背景,进展以及已知结果给出一个比较全面的综述.对于k≥ 2,我们定义σk（G）=min{∑i=1k d（xi）| {x1,,xk}是G的独立集}.1.控制圈如果V（G）\V（C）中的每个点在C中都有一个邻点,并且V（G）\V（C）是一个独立集,则称C是控制圈.第2章,我们关注度和与图中每个最长圈都是控制圈的问题.事实上,如果diff（G）=p（G）-c（G）≤ 1,则每个最长圈是控制圈.在2007年,Liu 等[Graphs and Combinatorics,23（2007）,433-443]提出 了如下猜想:猜想1.设G是一个n阶k-连通图且k≥ 2.如果σk+1（G）>（kk+1）（n+1）/3,则diff（G）≤1.猜想 1 对于 k=2 和 k=3 分别被 Enomoto 等[Journal of Graph Theory,20（1995）,213-225]和Liu等[Graphs and Combinatorics,23（2007）,433-443]解决.然而k≥ 4的情形至今未被解决.解决kk=2,3采取的技巧是在最长路上找到期望的独立集,这个技术很难推广到一般的k-连通图上.另外,diff（G）≤ 1这个要求更加严苛,其中有关diff（G）≤ 1的结果只有几篇.因此,猜想1的难度之大可见一斑.于是,我们提出了如下问题:问题1.设G是一个n阶k-连通图且k>2.如果σk+1（G）>（k+1）（n+1）/3,则每个最长圈是控制圈?如果问题1的回答是否定的,说明猜想1是错误的;如果回答是肯定的,从侧面支持猜想1的正确性.事实上,问题1对于k≥ 4是未知的.1980年Bondy的一个经典结果说明问题1对于k=2是正确的.定理A.设G是一个n阶2-连通图.如果σ3（G）>n+1,则每个最长圈是控制圈.Lu 等在文章[Journal of Graph Theory,49（2005）,135-150]中的一个结果说明问题1对于k=3是正确的.定理B.设G是一个n阶3-连通图.如果σ4（G）>（4n+4）/3,则每个最长圈是控制圈.在第2章中,基于对问题1的兴趣以及受定理B的启发,我们最终对问题1给出了肯定的回答.洞悉到定理B采取的扩圈技巧和估算三种类型的3独立集的度和的技术可以改进并加以推广.我们主要研究k-连通非Hamiltonian图的性质,找到一类不可嵌入点集,估算四种类型的3独立集的度和.主要结果如下.定理1.设G是一个n阶k-连通图且k≥ 2.如果σk+1（G）>（kk+1）（n+1）/3,则每个最长圈是控制圈.我们通过构造一类图说明σk+1（G）的界是紧的.一方面,在定理1中,取k=1,2,我们将分别得到定理A和定理B.换句话说,我们的结果蕴含了定理A和定理B.另一方面,我们的结果对猜想1的正确性提供了支持.2.扫把树第3章,我们关注度和与包含有限个分支点的生成树问题.树中度大于等于3的点称为分支点.包含有限个分支点的生成树的存在性问题是图论中广义traceability问题.事实上,它是一个NP-hard问题.把星的中心与一条路的端点粘在一起得到的树称为扫把树.虽然扫把树至多有一个分支点,但是判断一个图是否包含生成扫把树问题是NP-complete问题.因此,研究这个课题唯一可行的方法就是探索包含有限个分支点的生成树存在性的充分条件.Chen 等[Journal of Graph Theory,77（2014）,237-250]提出 了如下猜想:猜想2.设G是一个n ≥ 3阶连通图.如果σ3（G）≥-2,则G包含一个生成的扫把树.在第3章中,熟练运用Hamiltonian理论的一些重要结果,巧妙运用度和条件以及最长路或圈的极大性分析结构,我们证实了猜想2对于n>50是成立的.另外,我们通过构造一类图说明σ3（G）的界是紧的.主要结果如下:定理2.设G是一个n阶连通图且n>50.如果σ3（G）≥n-2,则G包含一个生成的扫把树.3.正常连通数在第4章中,我们关注度和与正常连通数为2的广义边染色问题.如果一个边着色图G中任意两u,v∈ V（G）点间都有一条正常长染色的（u,v）-路,则称G是正常连通的.使得G正常连通所需最少颜色的数目,称为正常连通数,用pc（G）表示.如果图G有一个k-边染色c使得对任意u,v∈V（G）,都有两条正常染色的（u,v）-路P=ux1…xkv和P’=uy1…ylv并且 c（ux1）≠c（uy1）和c（vxk）≠c（vye）,则称 G是 kk-strong 的.Borozan等[Discrete Mathematics,312（2012）,2550-2560]猜想:δ（G）≥3的2-连通图G的pc（G）=2.虽然这个猜想被Huang等[Discrete Mathematics,340（2017）,2217-2222]和 Brause 等[Graphs and Combinatorics,33（2017）,833-843]分别否定了,但是它也提供了研究pc（G）=2的2-连通图G的一个思路.令δ（n）表示在δ（G）≥δ（n）且pc（G）=2的n阶2-连通非完全图中最小可能取值.一个有趣的问题是:δ（n）的准确值是多少?Brause等通过构造反例为δ（n）建立了下界,而上界的证明源于他们的一个定理.定理 C.n/42<δ（n）≤（n+28）/20.对于连通图来说,Borozan等从最小度方向考虑了类似问题并建立了一个紧的界:如果 δ（G）≥|G|/4,则 pc（G）=2.Chang 等[Ars Comibinatorics,147（2019）,161-171]通过放松了该结果中的最小度条件扩大了正常连通数为2的连通图的范围:定理D.设G是一个n≥9阶连通图且G≠Kn.如果σ2（G）≥n/2,则pc（G）=2.在第4章,受Brause等和Huang等构造反例的启发,我们首先构造了正常连通数大于等于3的一类图,其中一张图的δ（G）=n/36.因此,我们有定理 3.δ（n）>n/36.其次,基于Chvatal和Erdos定理,我们进一步很自然地放松了定理D的约束条件,进一步扩大了正常连通数为2的连通图的范围,证明了定理4.这里我们排除了 pc（G）≥ 3的R1,3连通图G.一个连通图G称为R1,3的,如果存在割点v使得|Bv| ≥3,其中Bv={B:B是G的块,v∈ V（B）,B≤ 3},否则G称为R1,3-free的.我们的主要想法是:将图划分成几个点导出子图,利用其中一个子图具有2-strong的性质,把它们连接起来得到一个pc（R）≤2的生成子图R.定理4.设G是一个R1,3 free的n>48阶连通图且G≠Kn.如果σ3（G）≥3n/4,则 pc（G）=2.4.离心连通指数在第5章中,我们主要研究有关离心连通指数的极值问题.点v的离心率即为ε（v）=max{d（u,v）:u ∈V（G）}.离心连通指数用ξc（G）表示,其定义如下:#12其中ω（uv）=ε（u）+ε（v）称为边uv的权.目前只有部分图类的离心连通指数的极值问题已经被研究.Zhou和Du[MATCH.Communications in Mathematical and in Computer Chemistry,63（2010）,181-198]以及 Morgan 等[Discrete Mathematics,311（2011）,1229-1234]分别独立证明了:星是n阶连通图图中唯一取得离心连通指数下确界的极图,路是取得n树中上界的极图.在同一文章,Zhou和Du还刻画了n阶单圈图的下确界.下面的定理5-8是我们在第5章的主要结果.我们首先考虑给定阶数和最小度的图类的下确界来改进连通图的已有结果.主要应用如下事实:当△（G）≤ n-2时,对任意的v∈ V（G）,有ε（v）≥2;当△（G）=n-1时,对任意的d（v）=△（G）,有ε（v）=1,对任意的 d（u）<△（G）,有 ε（u）=2,这里u,v∈V（G）.定理5.设G是一个n阶连通图且n ≥ 2δ2-2δ+4,δ（G）=δ.则ξc（G）≥（2δ+1）n-2δ-1当δ是奇数或者δ是偶数且n是奇数,等号成立当且仅当π（G）=（n-1,δ,δ,,δ）,ξc（G）≥（2δ+1）n-2δ+1 当δ是偶数且n是偶数,等号成立当且仅当 π（G）=（n-1,6+1,δ,,δ）.其次,我们刻画了在给定度序列的n阶树中取得离心连通指数上下确界极图的结构.这两个结果主要是利用图变换的思想.定理6.在所有非增度序列为（d1,d2,,dn）的n阶树中,greedy caterpillar的离心连通指数达到最大.定理7.在所有非增度序列为（d1,d2,,dn）的n阶树中,greedy tree的离心连通指数达到最小.最后,我们考虑给定阶数和半径的单圈图的下确界来扩展单圈图的结果.主要思想是利用公式ξc（G）=∑uv∈E（G）w（uv）并通过分析结构估算每条边权的最小可能取值.定理8.设G是一个给定半径rad（G）=r ≥2的n阶单圈图.（i）如果2r ≤ n ≤ 2r+1,则ξc（G）≥2nr,等号成立当且仅当G（?）=Cn.（ii）如果 n ≥ 2r+2,则 ξc（G）≥ 2rn+n-2r+2 当 n ≤ 3r-2,等号成立当且仅当G（?）U2rn;ξc;ξc（G）≥ 2rn+n-2r+1当n≥3r-1,等号成立当且仅当G∈y2r1.