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

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

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

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

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

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

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

7、研究現(xiàn)狀.
　　 在第二章中，我們研究了Schrijver圖SG(2k+2，k)的線性蔭度和點(diǎn)線性蔭度.得到了SG(2k+2，k)的結(jié)構(gòu)特征，并得到了下面兩個(gè)結(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.得到了如下兩個(gè)

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