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

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

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

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

4、k(G)]+1)-樹．他們還舉例說明這個上界對一般的連通圖而言是緊的．本文中，我們在笛卡兒積圖和直積圖上進一步研究度限定的支撐樹問題，并改進了他們的上界． 第二章我們研究笛卡兒積圖上度限定的支撐樹問題．設(shè)G<,1>和G<,2>是兩個圖，我們記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是一棵樹且u ∈V(T)．對一個給定的正整數(shù)k≥△(T)，我們定義函數(shù)f<,T>(u，k)：=k-d<,T>(v)為 v在T上對k的虧，F(xiàn)<,T>(k)：=∑<,v∈V(T)>f<,T>(u，K)為樹T對K的虧．設(shè)G<,i>是連通圖，T<,i>是G<,i>的一棵k<,i->樹(i=1，2)，其中|G<,2>|≥3并且k<,2>≥k<,1>．我們證

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

7、)．另外，我們還通過一些例子說明我們的上界優(yōu)于已有的上界. 第三章我們研究直積圖上度限定的支撐樹問題．我們記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>中相鄰，同時v與v’在G<,2>中相鄰．設(shè)G<,1>是一個包含奇圈的連通圖，G<,2>包含Hamilton路

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