李海萍 楊英

摘 要：為了更好地研究頻道分配問題，引入了從頂點集到非負(fù)整數(shù)集的一個函數(shù)，即圖的一個L（2，1）—標(biāo)號。假設(shè)最小標(biāo)號為零，圖的L（2，1）—標(biāo)號數(shù)就是此圖的所有L（2，1）—標(biāo)號下的跨度的最小數(shù)。對于路和圈的Cartesian積圖的推廣圖——手鐲圖的標(biāo)號數(shù)問題，給出了手鐲圖的定義，即是將擬梯子的兩端重合而得到的圖形，同時給出了其L（2，1）—標(biāo)號數(shù)的定義，運用頂點分組標(biāo)號法，根據(jù)圈的個數(shù)和每個圈的頂點數(shù)的不同進(jìn)行分類討論，研究結(jié)果完全確定了手鐲圖的L（2，1）—標(biāo)號數(shù)的確切值，豐富了圖的種類并完善了標(biāo)號數(shù)理論。

關(guān)鍵詞：圖論；L（2，1）-標(biāo)號；L（2，1）-標(biāo)號數(shù)；擬梯子；手鐲圖

中圖分類號：O157.5 MSC（2010）主題分類：05C78 文獻(xiàn)標(biāo)志碼：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

研究結(jié)果豐富了圖的種類并完善了標(biāo)號數(shù)理論，為實際應(yīng)用——頻道分配問題的研究提供了理論基礎(chǔ)。

參考文獻(xiàn)/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）—標(biāo)號[J].遼寧大學(xué)學(xué)報（自然科學(xué)版），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.