笛卡兒積圖和直積圖上的度限定支撐樹(shù).pdf

1、對(duì)給定的正整數(shù)k，連通圖G的一棵支撐樹(shù)T滿足△(T)≤k被稱(chēng)為圖G的一棵k-樹(shù)．對(duì)給定的連通圖G，確定極小可能的正整數(shù)k使得G包含一棵k-樹(shù)，即所謂度限定的支撐樹(shù)問(wèn)題．該問(wèn)題作為圖因子(即支撐子圖)問(wèn)題的一部分(即[1，k]-因子)，長(zhǎng)期以來(lái)受到人們的廣泛關(guān)注．本文是在笛卡兒積圖和直積圖上研究度限定的支撐樹(shù)問(wèn)題． 在第一章中，我們首先介紹了圖因子問(wèn)題，進(jìn)而介紹了本文的研究背景和我們的主要結(jié)果．圖因子問(wèn)題是圖論中一個(gè)經(jīng)典問(wèn)題，其歷

2、史可追溯到1891年P(guān)etersen[16]有關(guān)圖可二因子化的重要論文，其后又有Hall，Konig，Tutte，Lovász等人做出了大量廣泛而深刻的結(jié)果．圖因子問(wèn)題也是離散數(shù)學(xué)中非?；钴S，廣受關(guān)注的研究方向之一．早在上世紀(jì)70年代，Gavey和Johnson[8]就已經(jīng)證明確定圖中k-樹(shù)存在性的問(wèn)題是NP-hard的．因此，給出圖含k-樹(shù)的充分條件是很有意義的．事實(shí)上，Chvátal和Erdos在1972年[6]證明了每個(gè)滿足條件|

3、G|≥3且K(G)≥α(G)的圖G都有Hamilton圈．因此，圖G就有一條Hamilton路T作為其支撐樹(shù)．此時(shí)，△(T)≤[α(G)/k(G)]+1=2．這使得人們猜測(cè)K=[α(G)/k(G)]+1可能就是一般連通圖的K-樹(shù)中K的最小上界．Jackson和Wormald，Neumann-Lava和Rivera-Campo分別在1990年[11]和1991年[15]用不同的方法證明了上述猜想，他們證明每個(gè)連通圖G都有一棵([α(G)/

4、k(G)]+1)-樹(shù)．他們還舉例說(shuō)明這個(gè)上界對(duì)一般的連通圖而言是緊的．本文中，我們?cè)诘芽▋悍e圖和直積圖上進(jìn)一步研究度限定的支撐樹(shù)問(wèn)題，并改進(jìn)了他們的上界． 第二章我們研究笛卡兒積圖上度限定的支撐樹(shù)問(wèn)題．設(shè)G<,1>和G<,2>是兩個(gè)圖，我們記G<,1>和G<,2>的笛卡兒積為G<,1>□G<,2>，其中V(G<,1>□G<,2>)：=V(G<,1>)×V(G<,2>)，并且(u，v)與(u’，v')在G<,1>□G<,2>中相鄰

5、當(dāng)且僅當(dāng)u=u’且v與v’在G<,2>中相鄰，或者v=v’且u與u’在G<,1>中相鄰．設(shè)T是一棵樹(shù)且u ∈V(T)．對(duì)一個(gè)給定的正整數(shù)k≥△(T)，我們定義函數(shù)f<,T>(u，k)：=k-d<,T>(v)為 v在T上對(duì)k的虧，F(xiàn)<,T>(k)：=∑<,v∈V(T)>f<,T>(u，K)為樹(shù)T對(duì)K的虧．設(shè)G<,i>是連通圖，T<,i>是G<,i>的一棵k<,i->樹(shù)(i=1，2)，其中|G<,2>|≥3并且k<,2>≥k<,1>．我們證

6、明，如果F<,T<,1>>≥K<,2>，則G<,1>□G<,2>有棵K<,1>-樹(shù)；否則G<,1>□G<,2>有棵K<,2>-樹(shù)．進(jìn)一步的，我們證明，如果|T<,1>|≥K<,2>-K<,1>+1那么G<,1>□G<,2>就有一棵K<,1>-樹(shù)．設(shè)G是一個(gè)連通圖且|G|≥3，又設(shè)r是一個(gè)實(shí)數(shù)滿足r．k(G)≥δ(G)且α(G)≥2r．我們證明G□G有一棵([α(G)/k(G)]+1)-樹(shù)，并且α(G□G)/k(G□G)>α(G)/k(G

7、)．另外，我們還通過(guò)一些例子說(shuō)明我們的上界優(yōu)于已有的上界. 第三章我們研究直積圖上度限定的支撐樹(shù)問(wèn)題．我們記G<,1>和G<,2>的直積為G<,1>×G<,2>，其中V(c<,1>×G<,2>)：=V(G<,1>)×V(G<,2>)，并且(u，v)與(u’，v’)在G<,1>×G<,2>中相鄰當(dāng)且僅當(dāng)u與u'在G<,1>中相鄰，同時(shí)v與v’在G<,2>中相鄰．設(shè)G<,1>是一個(gè)包含奇圈的連通圖，G<,2>包含Hamilton路

8、且有偶數(shù)個(gè)頂點(diǎn)．我們證明，如果G<,1>有棵k-樹(shù)，則G<,1>×G<,2>就有一棵(k+1)一樹(shù)．更進(jìn)一步，如果G<,1>有棵k-樹(shù)T使得T+uu'包含一個(gè)奇圈(uu’∈E(G<,1>)\E(T))，其中u，u’∈V(T)滿足d<,T><Δ(T)且d<,T>(u’)<△(T)，那么G<,1>×G<,2>就包含一棵k-樹(shù)．我們還證明，如果G是一個(gè)非Hamilton圖，滿足G包含奇圈且δ(G)≥1，并且有某個(gè)正整數(shù)n使得n．k(G)≥δ(