手鐲圖的L（2，1）—標號

李海萍 楊英

摘 要：為了更好地研究頻道分配問題，引入了從頂點集到非負整數集的一個函數，即圖的一個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.