關于根點對稱的二元樹的多級距離標號

侯麗霞，左連翠

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

關于根點對稱的二元樹的多級距離標號

侯麗霞，左連翠

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

研究關于根點對稱的二元樹的多級距離標號，得到了其多級距離數(shù)的一般下界，以及一類特殊的關于根點對稱的二元樹的多級距離數(shù)的確切值.

多級距離數(shù)；多級距離標號；關于根點對稱的二元樹

多級距離標號也稱電臺標號，是L（2 ，1）標號的拓展，它們都源于Hale的無線電頻道分配問題.給定一個電臺的集合，一個有效的頻道分配是一個函數(shù)，它分配給每個電臺一個頻道，且使這些頻道避免相互干擾.頻道間相互干擾程度與電臺的位置有關，即電臺距離越近，干擾就越強烈.為了避免相互干擾，距離越近的電臺，頻道差就應該越大，從而頻道差由電臺間的距離決定.上述問題可用圖模擬表示，即把每一個電臺視為圖的一個點，每一對相鄰的電臺在圖中相應的點之間都連以邊.

圖的多級距離標號是一個非常有趣卻較困難的組合問題，迄今為止有很多學者對它進行了研究.文獻［1］－［3］主要研究了路和圈的多級距離數(shù)，最終由Liu等完全解決［4］.后來，Liu等對平方圈的多級距離數(shù)進行了研究［5］，在得到大部分平方圈的多級距離數(shù)的同時，也得到其余平方圈的多級距離數(shù)的下界.2008年，Liu又給出了樹的多級距離數(shù)的下界，并得到一類特殊的樹——“蜘蛛”（至多有一個頂點的度大于2的樹）的多級距離數(shù)［6］.2010年，Li等給出了完全m元樹的多級距離標號［7］.

1 關于根點對稱的二元樹的多級距離數(shù)的一般下界

圖1 T2，2，4，4，6Figure 1 T2，2，4，4，6

下面將文獻［7］中關于完全二元樹的多級距離數(shù)的下界推廣到關于根點對稱的二元樹，其中葉子點的個數(shù)起著非常重要的作用.

2 一類特殊的關于根點對稱的二元樹的多級距離數(shù)

圖2 T2，4，6，8，8Figure 2 T2，4，6，8，8

［1］ Chartr G，Erwin D，Harary F，et al.Radio labelings of graphs［J］.Bull Inst Combin Appl，2001，33：77－85.

［2］ Chartr G，Erwin D，Zhang P.A graph labeling problem suggested by FM channel restriction［J］.Bull Inst Combin Appl，2005，43：43－57.

［3］ Zhang P.Radio number of cycles［J］.Ars Combin，2002，65：21－32.

［4］ Liu D，Zhu X.Multi－level distance labelings for paths and cycles［J］.SIAM J Disc Math，2005，19：610－621.

［5］ Liu D，Xie M.Radio number for square cycles［J］.Congr Number，2004，169：105－125.

［6］ Liu D.Radio number for trees［J］.Disc Math，2008，308：1153－1164.

［7］ Li X，Mak V，Zhou S.Optimal radio labellings of completem－ary trees［J］.Discrete Applied Math，2010，158：507－515.

Multi－level distance labeling of symmetric binary tree about root

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

The multi－level distance labeling of symmetric binary tree about root is studied.The general lower bound of its multi－level distance number and the exact value of multi－level distance number of a special class of symmetric binary tree about root are obtained.

multi－level distance number；multi－level distance labeling；symmetric binarytree about root

O157.5

A

1671－1114（2011）03－0022－07

2010－12－30

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

侯麗霞（1985—），女，碩士研究生.

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

（責任編校 馬新光）