圖的頂點標號.pdf

1、本文論述了圖的頂點標號?！　　〗o定一個無向圖G，G的一個L(2，1)-labeling是指從其頂點集V(G)到非負整數(shù)集的一個映射f，滿足：|f(x)-f(y)|≥{21當dG(x,y)=l當dG(x,y)=2這里dG(u，v)表示u和v之間的距離，即u和v之間最短路的長度。象集合中的元素稱為標號。若一個L(2，1)-labeling中的所有標號都不超過整數(shù)k，則稱之為k-L(2，1)-labeling。圖G的L(2，1)-label

2、ing數(shù)，記作λ(G)，是使得圖G存在k-L(2，1)-labeling的最小整數(shù)k。特別地，若G的某個L(2，1)-labeling中的標號是連續(xù)出現(xiàn)的，則稱之為G的一個No-holeL(2，1)-labeling。圖G的No-holeL(2，1)-labeling數(shù)，記作-λ(G)，是使得圖G存在No-holek-L(2，1)-labeling的最小整數(shù)k。由定義易知，如果一個n階圖G存在No-holeL(2，1)-labeling

3、，則λ(G)≤λ(G)≤n-1。 　根據(jù)n階圖G的邊數(shù)，連通分支數(shù)和直徑給出了Gc存在哈密頓路和哈密頓圈的充分條件，從而相應地得到了G存在No-holeL(2，1)-labeling的充分條件。然后根據(jù)這三個參數(shù)刻畫了λ(G)=n-1的圖。主要結果有：(1)設G是階數(shù)n邊數(shù)m的簡單圖，如果m≤n-2或其連通分支數(shù)p(G)≥「(n+1)/2」或G是直徑d≥[n/2]+l的連通圖，則Gc有哈密頓路，從而G有No-holeL(2，1)-

4、labeling。(2)設G是n個頂點m條邊的圖，如果λ(G)=n-1，則n-2≤m≤(n-1)(n-2)/2。此外對任意滿足n≥3且n-2≤m≤(n-1)(n-2)/2的整數(shù)n和m，存在階數(shù)n邊數(shù)m的簡單圖G使得λ(G)=n-l，并且邊數(shù)為n-2和(n-1)(n-2)/2的圖是確定的。(3)設G是n階簡單圖，如果λ(G)=n-l，則p(G)≤[n/2]。此外對任意滿足n≥4且1≤p≤[n/2]的整數(shù)n和p，存在階數(shù)n連通分支數(shù)p的簡單

5、圖G使得λ(G)=n-1，并且分支數(shù)為「n/2]的圖是確定的。(4)設G是階數(shù)n≥6直徑d的連通圖，如果λ(G)=n-1，則2≤d≤[n/2]+l。此外對任意滿足n≥6且2≤d≤[n/2」+l的整數(shù)n和d，存在階數(shù)n直徑d的簡單圖G使得-λ(G)=n-1。(5)對任意滿足2≤k≤n-l的整數(shù)n和k，存在一個n階簡單圖G使得-λ(G)=k。 給定一個無向圖G及整數(shù)j≥k，G的一個L(j，k)-labeling是指從其頂點集V(G)

6、到非負整數(shù)集的一個映射f，滿足：|f(x)-f(y)|≥{jk當dG(x,y)=2當dG(x,y)=1若一個L(j，k)-labeling中的所有標號都不超過整數(shù)t，則稱之為t-L(j，k)-labeling。圖G的L(j，k)-labeling數(shù)，記作λj,k(G)，是使得圖G存在t-L(j，k)-labeling的最小整數(shù)t。有向圖D的L(j，k)-labeling數(shù)記作-λj，k(D)，其定義類似于無向圖G，只需將其中dG(u，v

7、)變?yōu)镈中從u到v的有向距離。 G.J.Chang等人[21-22]根據(jù)有向圖D中最長有向路的長度l(D)研究有向圖的L(j，k)-labeling問題，得到了一些非常好的結果。 證明了：(1)對任意一個有向圖D有-λj,k(D)≤(-x(D)-1)j，這里-x(D)表示D的有向著色數(shù)，并且界是可達到的；(2)對任意一個有向圖D，如果它不含有向圈或者其最長有向圈長度為l(D)+1，則-λj,k(D)≤lj，并且界是可達到

8、的。最后我們對l(D)=3且所含最長有向圈長不等于3的有向圖D給出了設置其3j-L(j，k)-labeling的一個有效算法。 研究了圖的L(3，2，1)-labeling問題。主要結果有：(1)設Pn為n個頂點的路，則當n=1時，λ3(Pn)=0；n=2時，λ3(Pn)=3；n=3，4時，λ3(Pn)=5；n=5，6，7時，λ3(Pn)=6；n≥8時，λ3(Pn)=7。(2)設Cn為n個頂點的圈，則當n=3，4，5時，λ3(C