圖的頂點(diǎn)標(biāo)號(hào).pdf

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

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

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

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

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

6、到非負(fù)整數(shù)集的一個(gè)映射f，滿(mǎn)足：|f(x)-f(y)|≥{jk當(dāng)dG(x,y)=2當(dāng)dG(x,y)=1若一個(gè)L(j，k)-labeling中的所有標(biāo)號(hào)都不超過(guò)整數(shù)t，則稱(chēng)之為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)，其定義類(lèi)似于無(wú)向圖G，只需將其中dG(u，v

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

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