李海萍 杨英

摘 要：为了更好地研究频道分配问题，引入了从顶点集到非负整数集的一个函数，即图的一个L（2，1）—标号。假设最小标号为零，图的L（2，1）—标号数就是此图的所有L（2，1）—标号下的跨度的最小数。对于路和圈的Cartesian积图的推广图——手镯图的标号数问题，给出了手镯图的定义，即是将拟梯子的两端重合而得到的图形，同时给出了其L（2，1）—标号数的定义，运用顶点分组标号法，根据圈的个数和每个圈的顶点数的不同进行分类讨论，研究结果完全确定了手镯图的L（2，1）—标号数的确切值，丰富了图的种类并完善了标号数理论。

关键词：图论；L（2，1）-标号；L（2，1）-标号数；拟梯子；手镯图

中图分类号：O157.5 MSC（2010）主题分类：05C78 文献标志码：A

文章编号：1008-1542（2018）04-0314-07doi：10.7535/hbkd.2018yx04004

Abstract：In order to better study the channel assignment problem， a function from the vertex set to the set of all nonnegative integers is generated， that is the L（2，1）—labeling of a graph. Let the least label be zero， the L（2，1）—labeling number of a graph is the smallest number over the spans of all L（2，1）—labeling of this graph. Aiming at the problem of the L（2，1）—labeling numbers of the bracelet graph， which is a generalized graph from Cartesian products of the path and cycles， the definition of the bracelet graph is given， which is obtained by overlapping the two ends of a similarity ladder. At the same time the definition of the L（2，1）—labeling numbers is given. The L（2，1）—labeling number is completely determined by vertex grouped labeling method according to the difference of the circles' numbers and the vertices' numbers of the circles. The types of graphs are enriched and the labeling number theories are perfected.

Keywords：graph theory； L（2，1）—labeling； L（2，1）—labeling number； similarity ladder； bracelet graph

研究結果丰富了图的种类并完善了标号数理论，为实际应用——频道分配问题的研究提供了理论基础。

参考文献/References：

[1] CHANG G J， KUO D. The L（2，1）—labeling problem on graphs[J]. SIAM Journal on Discrete Mathematics，1993， 15（2）： 309-316.

[2] GEORGES J P， MAURO D W. Generalized vertex labelings with a condition at distance two[J]. Congr Numerantium， 1995， 109： 141-159.

[3] GEORGES J P， MAURO D W. Some results on λj，k-numbers of the products of complete graphs[J]. Congr Numerantium， 1999， 140： 141-160.

[4] GEORGES J P， MAURO D W， STEIN M I. Labeling products of complete graphs with a condition at distance two[J]. SIAM Journal on Discrete Mathematics， 2001， 14（1）： 28-35.

[5] GEORGES J P， MAURO D W， WHITTLESEY M A. Relating path coverings to vertex labelings with a condition at distance two[J]. Discrete Mathematics， 1994， 135（1/2/3）： 103-111.

[6] GRIGGS J R， YEH R K. Labeling graphs with a condition at distance 2[J]. SIAM Journal on Discrete Mathematics， 2006， 5（4） ： 586-595.

[7] JHA P K， NARAYANAN A， SOOD P， et al. On L（2，1）—labeling of the Cartesian product of a cycle and a path[J]. Ars Combinatoria， 2000， 55： 81-89.

[8] YEH R K. A survey on labeling graphs with a condition at distance two[J]. Discrete Mathematics， 2006， 306（12）： 1217-1231.

[9] BORODIN O V， KOSTOCHKA A V， WOODALL D R. Total colorings of planar graphs with large maximum degree[J]. Journal of Graph Theory， 1997， 26（1）： 53-59.

[10]BORODIN O V， KOSTOCHKA A V， WOODALL D R. List edge and list total colourings of multigraphs[J]. Journal of Combinational Theory Ser B， 1997， 71（2）： 184-204.

[11]BORODIN O V， KOSTOCHKA A V， WOODALL D R. Total colorings of planar graphs with large girth[J]. Europe Journal Combination， 1998， 19（1）： 19-24.

[12]ISOBE S， ZHOU X， NISHIZEKI T. Total colorings of degenerated graphs[J]. Combinatorica， 2001， 100（2）： 506-517.

[13]ROSENFELD M. On the total coloring of certain graphs[J]. Israel Journal of Mathematics， 1971， 9（3）： 396-402.

[14]VIJAVYADITYA N. On total chromatic number of a graph[J]. Journal of the London Mathematical Society， 1971， 2/3（3）： 405-408.

[15]LYU Damei， LIN Nianfeng. L（d，1）—labelings of edge-path-replacement of a graph[J]. Journal of Combinatorial Optimization， 2013， 26（4）： 819-831.

[16]KUO D， YAN J H. On L（2，1）—labeling of cartesian products of paths and cycles[J]. Discrete Mathematics， 2004， 283（1）： 137-144.

[17]WHITTLESEY M A， GEORGES J P， MAURO D W. On the -number of Qn and related graphs[J]. SIAM Journal on Discrete Mathematics， 1995， 8（4）： 499-506.

[18]LYU Damei， LIN Nianfeng， YAN Dongmei. L（d，1）—labelings of the mbius ladders[J]. Journal of Zhejiang University（Science Edition）， 2011， 38（3）：256-261.

[19]杜鵑，吕大梅，李冬冬，等.拟梯子的L（2，1）—标号[J].辽宁大学学报（自然科学版），2013，40（4）：308-313

DU Juan， LYU Damei， LI Dongdong， et al. The L（2，1）—labelings of the similarity ladders[J]. Journal of Liaoning University（Natural Sciences Edition）， 2013， 40（4）：308-313.

[20]LYU Damei， SUN Jianping. L（2，1）—labelings of the edge-multiplicity-paths-replacement of a graph[J]. Journal of Combinatorial Optimization， 2016， 31（1）：396-404.