笛卡儿积图和直积图上的度限定支撑树

论文摘要

对给定的正整数k,连通图G的一棵支撑树T满足Δ（T）≤k被称为图G的一棵k-树.对给定的连通图G,确定极小可能的正整数k使得G包含一棵k-树,即所谓度限定的支撑树问题.该问题作为图因子（即支撑子图）问题的一部分（即[1,k]-因子）,长期以来受到人们的广泛关注.本文是在笛卡儿积图和直积图上研究度限定的支撑树问题.在第一章中,我们首先介绍了图因子问题,进而介绍了本文的研究背景和我们的主要结果.图因子问题是图论中一个经典问题,其历史可追溯到1891年Petersen [16]有关图可二因子化的重要论文,其后又有Hall, K¨onig, Tutte,Lov′asz等人做出了大量广泛而深刻的结果.图因子问题也是离散数学中非常活跃,广受关注的研究方向之一.早在上世纪70年代, Garey和Johnson [8]就已经证明确定图中k-树存在性的问题是NP-hard的.因此,给出图含k-树的充分条件是很有意义的.事实上, Chv′atal和Erd¨os在1972年[6]证明了每个满足条件|G|≥3且κ（G）≥α（G）的图G都有Hamilton圈.因此,图G就有一条Hamilton路T作为其支撑树.此时,Δ（T）≤「（α（G））/（κ（G））」+ 1 = 2.这使得人们猜测k =「（α（G））/（κ（G））」+ 1可能就是一般连通图的k-树中k的最小上界. Jackson和Wormald,Neumann-Lara和Rivera-Campo分别在1990年[11]和1991年[15]用不同的方法证明了上述猜想,他们证明每个连通图G都有一棵「（α（G））/（κ（G））」+ 1 -树.他们还举例说明这个上界对一般的连通图而言是紧的.本文中,我们在笛卡儿积图和直积图上进一步研究度限定的支撑树问题,并改进了他们的上界.第二章我们研究笛卡儿积图上度限定的支撑树问题.设G1和G2是两个图,我们记G1和G2的笛卡儿积为G1□G2,其中V （G1□G2） :=V （G1）×V （G2）,并且（u,v）与（u ,v ）在G1□G2中相邻当且仅当u = u且v与v在G2中相邻,或者v = v且u与u在G1中相邻.设T是一棵树且v∈V （T）.对一个给定的正整数k≥Δ（T）,我们定义函数fT（v,k） := k - dT（v）为v在T上对k的亏, FT（k） :=∑v∈V（T）fT（v,k）为树T对k的亏.设Gi是连通图, Ti是Gi的一棵ki-树（i = 1,2）,其中|G2|≥3并且k2≥k1.我们证明,如果FT1（k1）≥k2,则G1□G2有棵k1-树;否则G1□G2有棵k2-树.进一步的,我们证明,如果|T1|≥k2 - k1 + 1那么G1□G2就有一棵k1-树.设G是一个连通图且|G|≥3,又设r是一个实数满足r·κ（G）≥δ（G）且α（G）≥2r.我们证明G□G有一棵「（α（G））/（κ（G））」+ 1 -树,并且（α（G□G））/（κ（G□G）） > （α（G））/（κ（G））.另外,我们还通过一些例子说明我们的上界优于已有的上界.第三章我们研究直积图上度限定的支撑树问题.我们记G1和G2的直积为G1×G2,其中V （G1×G2） := V （G1）×V （G2）,并且（u,v）与（u ,v ）在G1×G2中相邻当且仅当u与u在G1中相邻,同时v与v在G2中相邻.设G1是一个包含奇圈的连通图, G2包含Hamilton路且有偶数个顶点.我们证明,如果G1有棵k-树,则G1×G2就有一棵（k + 1）-树.更进一步,如果G1有棵k-树T使得T + uu包含一个奇圈uu∈E（G1） E（T） ,其中u,u∈V （T）满足dT（u） <Δ（T）且dT（u ） <Δ（T）,那么G1×G2就包含一棵k-树.我们还证明,如果G是一个非Hamilton图,满足G包含奇圈且δ（G）≥1,并且有某个正整数n使得n·κ（G）≥δ（G）,那么(α(G×P2n))/(κ(G×P2n)) > （α（G））/（κ（G）） + 1.另外,我们通过一些例子说明我们的上界优于已有的上界.

论文目录

• 摘要
• Abstract
• 1. Introduction
• 1.1 Notation
• 1.2 k-Tree
• 2. Degree Bounded Spanning Tree of a Cartesian Product
• 2.1 Main Result
• 2.2 To Compare the Two Bounds
• 3. Degree Bounded Spanning Tree of a Direct Product
• 3.1 Main Result
• 3.2 To Compare the Two Bounds
• 4. Bibliography
• 5. Contents of finished papers
• 6. Acknowledgement