圖的線性蔭度和線性K-蔭度.pdf

1、圖的染色理論一直是圖論界的一個熱門話題.一個圖G的k-邊染色是從E(G)到{1，2，…，k}的一個映射f.對于圖G一個給定的k-邊染色，Ei表示G中染i色的邊的集合，而G[Ei]]表示Ei在G中的邊導(dǎo)出子圖.若Ei(1≤i≤k)都是匹配，則稱f為一個正常k-邊染色.使得圖G有正常k-邊染色的最小數(shù)k稱為圖G的邊色數(shù)，記為x'(G).在一個k-邊染色中，若G[Ei](1≤i≤k)的每個連通分支都是路，則稱f為一個k-線性染色.使得圖G有k

2、-線性染色的最小的數(shù)k稱為圖G的線性蔭度，記為la(G).
　　 一個圖G的k-染色是從V(G)到{1，2，…，k}的一個映射f.對于圖G一個給定的k-染色，Vi表示G中染i色的頂點的集合，而G[Vi]表示Vi在G中的點導(dǎo)出子圖.若Vi(1≤i≤k)都是獨立集，則稱f為一個正常k-染色.使得圖G有正常k-染色的最小數(shù)k稱為圖G的點色數(shù)，記為x(G).在一個k-染色中，若G[Vi](1≤i≤k)的每個連通分支都是路，則稱f為一個路

3、k-染色.使得圖G有路k-染色的最小的數(shù)k稱為圖G的點線性蔭度，記為vla(G).
　　 一個圖G的線性k-森林為圖G的一個子圖，其中，它的每個連通分支為長度至多為k的路.線性k-蔭度lak(G)即為分解圖G的邊集E(G)所需要的線性k-森林的最小個數(shù).事實上，線性k-蔭度為邊著色的一種自然的推廣.顯然，線性1-森林為一個匹配，所以，la1(G)即為圖G的邊色數(shù)x'(G).當(dāng)線性k-森林中的路的長度不受限制時(k=∞)，記la∞

4、(G)為la(G)，稱為圖G的線性蔭度.
　　 給定一個n元集合[n]={0，1，…，n-1}，S為[n]的一個子集，若對于任意兩個不同元素x，y∈S滿足2≤| x-y|≤n-2，則稱S為一個2-穩(wěn)定子集.一個圖為Schrijver圖SG(n，k)，如果它的頂點集是由n元集合[n]={0，1，…，n-1}的所有k元2-穩(wěn)定子集構(gòu)成的，并且兩個頂點相鄰當(dāng)且僅當(dāng)它們所對應(yīng)的兩個集合不交.
　　 一個完全n部圖稱為均衡的，如果

5、它的頂點集的每個劃分都有相同的頂點個數(shù).我們記Kn(m)為一個均衡完全n部圖，其中頂點集的每個劃分中有m個頂點.
　　 假設(shè)G1,G2，…，Gm為m個圖，則圖G=G1□G2□…□Gm稱為圖G1，G2，…，Gm的笛卡爾積圖，其中，G的頂點集為∏mi=1 V(Gi)，并且兩個頂點(u1，u2，…，um)and(v1，v2，…，vm)相鄰當(dāng)且僅當(dāng)存在一個j滿足ujvj∈E(Gj)，并且對于其他的i≠j有ui=vi.當(dāng)Gi=G(i=1，

6、2，…，m)，我們記Gm=G1□G2□…□Gm.一些完全圖Kn1，，Kn2，…，Knm的笛卡爾積圖Kn1，□Kn2□…□Knm稱為一個Hamming圖.
　　 記Kn(m)，Kmn，SG(n，k)分別為均衡完全n部圖，Hamming圖Kn□Kn□…□Kn和Schrijver圖.記△(G)為圖G的最大度.
　　 本論文主要分以下四部分：
　　 在第一章中，我們引進了一些定義和符號，并且介紹了線性蔭度和線性k-蔭度的

7、研究現(xiàn)狀.
　　 在第二章中，我們研究了Schrijver圖SG(2k+2，k)的線性蔭度和點線性蔭度.得到了SG(2k+2，k)的結(jié)構(gòu)特征，并得到了下面兩個結(jié)論.
　　 結(jié)論：1.la(SG(2K+2,k))={3,k=2,[k+2/2],k≥3.
　　 結(jié)論：2.vla(SG(2k+2，k))=2.
　　 在第三章中，我們研究了Kn(m)和Kmn的線性k-蔭度，在這里，我們?nèi)=n-1.得到了如下兩個

8、非常好結(jié)論.
　　 結(jié)論：3.對于均衡完全n部圖Kn(m)，lan-1(Kn(m))=[mn/2].
　　 結(jié)論：4.對于Hamming圖Kmn， lan-1(Kmn)=[mn/2].
　　 在第四章中，我們研究了Cmn的線性2-蔭度，K6n,4n，K6n+1，4n，K6n，4n+1的線性4-蔭度.得到了如下幾個結(jié)論.
　　 結(jié)論：5.對于二部完全圖和m個n-圈的笛卡爾積圖，我們得到了：
　　 (