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

《笛卡儿积图和直积图上的度限定支撑树》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士研究生学位论文新疆大学论文题目(中文)：笛卡儿积图和直积图上的度限定支撑树论文题目(外文)：DegreeBoundedSpanningTreeofCartesianandDirectProduct研究生姓名：杜文学学科、专业：应用数学学位类‘别：理学硕士研究方向：图论及其应用导师姓名职称：黄琼湘教授论文答辩日期2007年6月3日学位授予日期年月日学位论文独创性声明本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法律意义上已属于他人的任何形式的研究

2、成果，也不包含本人己用于其他学位申请的论文或成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中做出了明确的说明并表示谢意。本人如违反上述声明，愿意承担由此引发的一切责任和后果。论文作者签名：不支虿日期：口，年亍月27日学位论文知识产权权属声明本人的学位论文是在学期间在导师指导下完成的，知识产权归属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然为新疆大学。本学位论文属于：保密口，在年解密后适用于本声明。不保密曰。(请在以上方

3、框内打“~／”)论文作者签字导师签字禾支孑缎日期：。7年j月2P曰吼叼年伯母{

4、．j摘要摘要1对给定的正整数k，连通图G的一棵支撑树r满足H(T)≤k被称为图G的一裸缸树．对给定的连通图G，确定极小可能的正整数k使得G包含一橡如树，即所谓度限定的支撑树闯题．该闯题作为图因子(即支撵子图)问题的一部分(即11，砰园子)，长期以来受到人们的广泛关注．本文是在笛卡凡积图和直积图上研究度限定的支撵树问题．在第一章中．我们首先介绍了图因子问题，进而介绍了本文的研究背景和我们的主要结果．图因子问题是图论中一个经典问题，其历史可追溯到1891年

5、Petersen}161有关图可二因子化的重要论文，其后又有Hall，KSnig，Tatte，Lov5sz等人做出了大量广泛面深刻的结果．图因子问题也是离散数学中非常活跃，广受关注的研究方向之一．早在上世纪70年代，Garey和Johnson【8】就已经证明确定图中如树存在性的闯题是NP-hard的．因此，给出图含船埘豹充分条件是很有意义的．事实上，Chv矗tal和Erd68在’1972年16】证明了每个满足条件IGI≥3且K(G)≥口(G)的图G都有Hamilton圈．因此，图G就有～条Hamilton路T作为其支撑树．此时，H

6、(T)≤『兰躲1+1=2．这使得人们猜测k=f躲1+1可能就是一般连通图的b树中k的最小上界．Jackson和Wormald，Nettmann-Lara和Rivera-Campo分别在1990年111l和1991年{15】用不同的方法证明了上述猜想，他们证明每个连通图G都有一棵(f黼]+1)·糖．他们还举例说明这个上界对一般的连通图面言是紧的。本文中，我们在笛卡儿积图和直积图上进一步研究度限定的支撑树闯题，并改进了他们的上界．第二章我们研究笛卡儿积图上度限定的支撑树问题．设Gl和Gj是两个图，我们记G1和G2的笛卡儿积为G1口G2

7、，其中’，(G1口G2)≈v(a1)×y(G2)，并且(札，F)与F，矿)在Gl凸G2中相邻当且仅当砧=盯且口与t，，在G2中相邻，或者"；t，，且牡与∥在Gl中相邻．设T是一棵树且t，∈y(T)．对一个给定的正整数k≥△(功，我们定义函数知(u，k)：-k一西(")为t，在T上对k的亏，昂(七)葛∑。∈y(刃，T(弘k)为树T对k的亏．设Gt是连通图，正是Q的一棵砖树“=1，2)，其中IG2l≥3并且如≥岛．我们证明，如果岛l陬)≥‰，则Gl口G2有棵‰一树；否则G1口G2有棵＆2-树．进一步的，我们证明，如果l五I≥如一h+1

8、那么G1口G2摘要2就有一棵h．树．设G是一个连通图且lq≥3，又设r是一个实数满足r·尤(G)≥6(G)且口(G)22r．我们证明G口G有一棵(f糕1+1)一树，并且詈《；{鲁>勰．另外，我们还通过一些例子说明我们的上界优于已有的上界．第三章我们研究直积图上度限定的支撑树闯题．我们记Gl和Q的直积为G1×G2，其中v(a1×G2)：=v(a1)×y(G2)，并且(t‘，口)与∥，∥)在G1×(＆中相邻当且仅当t‘与t，在G1中相邻，同时"与t，，在G2中相邻．设Gl是一个包含奇圈的连通图，岛包含Hamilton路且有偶数个顶点．

9、我们证明，如果G1有棵“树，则Gl×G2就有一棵(k+1)一树．更进一步，如果G1有棵缸树T使得T+伽7包含～个奇圈(t‘∥∈E(G1)＼E(T))，其中让，∥∈矿(印满足曲(u)