圖的一種特殊的（d，1）－全標號

張 煥，左連翠

（天津師范大學 數(shù)學科學學院，天津 300387）

圖的一種特殊的（d，1）－全標號

張 煥，左連翠

（天津師范大學 數(shù)學科學學院，天津 300387）

設圖G是有限的、無向的簡單圖.對于Δ（G）≥2d＋2的情況，給出了一種在［0，2Δ＋d－2］上d－好標號的方法，改進了相關(guān)文獻的結(jié)果.

（d，1）－全標號；d－好標號；跨度；（d，1）－全數(shù)

1 引言及預備知識

在進行電頻波分配時經(jīng)常出現(xiàn)這種情況：需要將電頻波分配給不同的傳輸站，每個傳輸站得到的電頻波是一個整數(shù).為了避免干擾，如果2個傳輸站距離較近，則它們接收的電頻波的波段要有一定的間隔.為了解決這個問題，文獻［1］定義了L（2，1）－標號.圖G的L（2，1）－標號是一個整數(shù)集到圖G的頂點的分配，滿足任意2個相鄰的頂點的標號之差至少為2，任意2個距離為2的頂點的標號互不相同.L（d，1）－標號［2］是L（2，1）－標號的一個自然推廣.而（d，1）－全標號［3］是L（d，1）－標號的一種特殊推廣，它由M.A.Whittlesey等首先提出.

2 主要結(jié)果

設圖G是有限的、無向的簡單圖.令A是V（G）的一個子集，B＝V（G）－A，［A，B］是一個邊集，并且［A，B］中任意邊滿足其2個端點分別在A，B中.稱［A，B］為圖G的一個割邊.稱圖G的所有割邊中邊數(shù)最多的割為圖G的最大割.令G（A）是A的導出子集，G（A）簡記為.

引理1［4］令圖G的最大度為2k＋1，則存在G的一個最大割［A，B］，滿足Δ）≤k，Δ）≤k.

引理2［4］令圖G的最大度為2k，則存在G的一個割［A，B］，滿足Δ）≤k－1，Δ）≤k.

引理2中的割實際上也是最大割.

引理3［4］令圖G是一個最大度為Δ的二部圖，則G存在一個在［1，Δ］中的邊著色c，使得邊e的標號c（e）≥i當且僅當e與一個度至少為i的頂點相關(guān)聯(lián).

從引理3的證明可以看出，若G是一個二部圖，則存在一個邊著色c，使得邊e的標號c（e）＝i當且僅當e與一個度至少為i的頂點相關(guān)聯(lián).當然，此時可以交換邊的顏色，使得c（e）＝j當且僅當e與一個度至少為i的頂點相關(guān)聯(lián)，其中i，j∈［0，Δ］.

引理4［4］令圖G的最大度Δ≤k，則G在［0，2k＋d－1］中存在一個（d，1）－全標號，使得頂點v得到的標號在［0，d（v）］中，邊的標號在［k＋d－1，2k＋d－1］中.

引理5［4］令圖G的最大度Δ≤k，則G在［0，2k＋d－1］中存在一個（d，1）－全標號，使得邊的標號在［0，k］中，頂點v得到的標號在［k＋d－1，k＋d－1＋d（v）］中.

文獻［4］給出了當d＝2時，G在［0，2Δ＋d－2］中有一個d－好標號，下面設d≥3.

定理1 如果Δ（G）＝2k＋1，并且k≥d，則G在［0，2Δ＋d－2］中有一個d－好標號.

根據(jù)引理3，對割［A，B］用［2k＋d，4k＋d］進行標號，使得邊e標2k＋d＋i當且僅當邊e與一個在G（［A，B］）中度至少為2k＋1－i的頂點相關(guān)聯(lián).因為Δ（G）＝2k＋1，則e與一個在或中度至多為i的頂點相關(guān)聯(lián)，其中i＝0，1，…，d－2.

對于［A，B］中的邊（a，b）的標號，除了（a，b）標2k＋2d－2－s并且b標2k＋d－1－j之外，其余的標號均滿足（d，1）－全標號的限制，其中，s＝0，1，…，d－2；j＝0，1，…，s.

這時，邊（a，b）標2k＋d＋i當且僅當a在中不大于i，其中i＝0，1，…，d－2，則0≤l（a）≤i.

下面對不滿足（d，1）－全標號限制的邊進行重新標號.

對于已標2k＋d＋i′的邊e，對e重新標k＋i′即可，其中i′＝1，2，…，d－2.對于標2k＋d的邊e，當2d－2≤k時，2k－d＋1≥k＋d－1，即2kd＋1在E）的標號段中，這時對e重新標2kd＋1，因為a在中是孤立點，所以重新標號是滿足（d，1）－全標號限制的；當d≤k＜2d－2時，如果邊e與一個標2k＋m的頂點b相關(guān)聯(lián)，則對邊e重新標k＋m，其中m＝1，2，…，d－1，因為k≥d并且a在中是孤立點，所以這種重新標號也是滿足（d，1）－全標號限制的.

其他邊和頂點保持標號不變.

在這個（d，1）－全標號中，每個頂點的標號都在［0，2k＋d－1］中，所以這個標號是G在［0，4k＋d］中的d－好標號.

定理2 如果Δ（G）＝2k≥2d＋2，則G在［0，2Δ＋d－2］上有一個d－好標號.

根據(jù)引理3，對割［A，B］用［2k＋d－1，4k＋d－2］進行標號，使得邊e標2k＋d－1＋i當且僅當邊e與一個在G（［A，B］）中度至少為2k－i的頂點相關(guān)聯(lián).因為Δ（G）＝2k，則e與一個在或中度至多為i的頂點相關(guān)聯(lián)，其中i＝0，1，…，d－2.

對于［A，B］中的邊（a，b）的標號，除了a標2k＋j并且邊（a，b）標2k＋d－1＋i，其中，j＝0，1，…，d－2，0≤i≤j（情況1），或者（a，b）標2k＋d－1并且b與中一個標2k＋d－1的邊相關(guān)聯(lián)（情況2）之外，其余的標號均滿足（d，1）－全標號的限制.

下面對部分邊和頂點重新著色.

情況1 由于k≥d，則（v）≥k＋j－d＋1≥i＋（k－d＋1）＞i.從而當（a，b）標2k＋d－1＋i時，b的標號不多于i.對于標2k＋d－1＋i′的邊（a，b），對其重新標k＋i′，其中i′＝1，2，…，d－2.對于標2k＋d－1的邊，如果k≥2d－1，則k＋d－1≤2k－d≤2k＋d－2，這時對邊（a，b）重新標2k－d；否則，對邊（a，b）重新標0，對b重新標k.這種重新標號是可以的，因為b在中是孤立點，并且0沒有在的邊標號中出現(xiàn).

情況2 此時b在中不是孤立點，從而a在中是孤立點.如果l（b）≥d，則對邊（a，b）重新標0.如果l（b）≤d－1并且k≥2d，則對邊（a，b）重新標2d－1.這種標號是可以的，因為3d－1＝2（d＋1）＋d－3≤2k＋d－3，并且3d－1＝2d＋d－1≥（k＋1）＋d－1＝k＋d，所以3d－1∈［k＋d，2k＋d－3］.從而，［A，B］中至多有（4d－2）－（2k＋d－1）＋1＝3d－2k≤d－2條邊不滿足（d，1）－全標號的限制，可如情況1一樣對這些邊重新標號.

其他邊和頂點保持標號不變.這樣得到了一個頂點標號均在［0，2k＋d－2］中的（d，1）－全標號.

由定理1—2可以得到下面的推論.

推論 如果Δ（G）≥2d＋2，則G在［0，2Δ＋d－2］中有一個d－好標號.

［1］ Griggs J R，Yeh R K.Labeling graphs with a condition at distance two［J］.SIAM J Discrete Math，1992，5：586－595.

［2］ Chang G J，Ke W，Liu D D，et al.On（d，1）－labelings of graphs［J］.Discrete Math，2000，220：57－66.

［3］ Whittlesey M A，Georges J P，Mauro D W.On theλ－number ofQnand related graphs［J］.SIAM J Discrete Math，1995，8：499－506.

［4］ Havet F，Yu M L.（p，1）－total labeling of graphs［J］.Discrete Math，2008，308：496－513.

［5］ Lih K W，Liu D D，Wang W F.On（d，1）－total numbers of graphs［J］.Discrete Math，2009，309：3767－3773.

A special（d，1）－total labeling of graph

ZHANGHuan，ZUOLiancui
（College of Mathematical Science，Tianjin Normal University，Tianjin 300387，China）

Gis a limited and undirected simple graph.A total labeling method is given to prove that for any graphGwithΔ（G）≥2d＋2，there is ad－good labeling ofGin［0，2Δ＋d－2］.And the results of related literatures are improved.

（d，1）－total labeling；d－good labeling；span；（d，1）－total number

O157.5

A

1671－1114（2011）02－0020－03

2010－04－07

天津師范大學引進人才基金資助項目（5RL066）

張 煥（1986—），女，碩士研究生.

左連翠（1964—），女，教授，博士，主要從事圖論與最優(yōu)化方面的研究.

（責任編校 馬新光）