关于根点对称的二元树的多级距离标号

侯丽霞，左连翠

（天津师范大学 数学科学学院，天津 300387）

关于根点对称的二元树的多级距离标号

侯丽霞，左连翠

（天津师范大学 数学科学学院，天津 300387）

研究关于根点对称的二元树的多级距离标号，得到了其多级距离数的一般下界，以及一类特殊的关于根点对称的二元树的多级距离数的确切值.

多级距离数；多级距离标号；关于根点对称的二元树

多级距离标号也称电台标号，是L（2 ，1）标号的拓展，它们都源于Hale的无线电频道分配问题.给定一个电台的集合，一个有效的频道分配是一个函数，它分配给每个电台一个频道，且使这些频道避免相互干扰.频道间相互干扰程度与电台的位置有关，即电台距离越近，干扰就越强烈.为了避免相互干扰，距离越近的电台，频道差就应该越大，从而频道差由电台间的距离决定.上述问题可用图模拟表示，即把每一个电台视为图的一个点，每一对相邻的电台在图中相应的点之间都连以边.

图的多级距离标号是一个非常有趣却较困难的组合问题，迄今为止有很多学者对它进行了研究.文献［1］－［3］主要研究了路和圈的多级距离数，最终由Liu等完全解决［4］.后来，Liu等对平方圈的多级距离数进行了研究［5］，在得到大部分平方圈的多级距离数的同时，也得到其余平方圈的多级距离数的下界.2008年，Liu又给出了树的多级距离数的下界，并得到一类特殊的树——“蜘蛛”（至多有一个顶点的度大于2的树）的多级距离数［6］.2010年，Li等给出了完全m元树的多级距离标号［7］.

1 关于根点对称的二元树的多级距离数的一般下界

图1 T2，2，4，4，6Figure 1 T2，2，4，4，6

下面将文献［7］中关于完全二元树的多级距离数的下界推广到关于根点对称的二元树，其中叶子点的个数起着非常重要的作用.

2 一类特殊的关于根点对称的二元树的多级距离数

图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—），女，教授，主要从事图论与最优化方面的研究.

（责任编校 马新光）