金 鑫，黨雪嬌，呂大梅

(南通大學(xué) 理學(xué)院，江蘇 南通 226007)

擬梯子的(2,1)-全標(biāo)號

金 鑫，黨雪嬌，呂大梅*

(南通大學(xué) 理學(xué)院，江蘇 南通 226007)

圖的一個(2,1)-全標(biāo)號指的是從點集和邊集到非負整數(shù)集的一個函數(shù)f，且使得：任兩個相鄰頂點標(biāo)號相異；任兩個相鄰邊標(biāo)號相異；以及任兩個關(guān)聯(lián)的點和邊標(biāo)號差至少為2.本文研究了擬梯子的(2,1)-全標(biāo)號,并完全確定了擬梯子的(2,1)-全標(biāo)號數(shù).

L(2,1)-標(biāo)號;(2,1)-全標(biāo)號；(2,1)-全標(biāo)號數(shù);擬梯子

0 引言

在通信波段分配問題的驅(qū)動下，誕生了距離2標(biāo)號問題.Griggs和Robert[1]在此問題基礎(chǔ)上，提出了圖的L(2,1)-標(biāo)號概念,并作了深入探討，可見綜述[2-4].

一個簡單圖G的L(2,1)-標(biāo)號指的是從頂點集V(G)到非負整數(shù)集的一個函數(shù)f，且使得d(u,v)=1時,|f(u)-f(v)|≥2；當(dāng)d(u,v)=2時，|f(u)-f(v)|≥1。不妨設(shè)最小標(biāo)號為0。則圖G所有L(2,1)-標(biāo)號下的跨度max{f(v);v∈V(G)}的最小值就是G的L(2,1)-標(biāo)號數(shù)，記為λ(G)。

1995年[5]，Whittlesty等對剖分圖的L(2,1)-標(biāo)號進行了研究。2002年[6-7]，Havet和Yu把剖分圖的L(2,1)-標(biāo)號稱為圖的(2,1)-全標(biāo)號，并將之推廣，進一步研究了圖的(d,1)-全標(biāo)號。接下來我們先給出(2,1)-全標(biāo)號的定義。

一個圖G的(2,1)-全標(biāo)號指的是從點集及邊集到非負整數(shù)集的一個函數(shù)f，且：任兩相鄰頂點標(biāo)號相異；任兩相鄰邊標(biāo)號相異；以及任關(guān)聯(lián)的點和邊標(biāo)號也相異。不妨設(shè)最小標(biāo)號為0。則G所有(2,1)-全標(biāo)號下的跨度max{f(v);v∈V(G)∪E(G)}的最小值為圖G的(2,1)-全標(biāo)號數(shù)，記為λT(G)。

文獻[8-11]研究了擬梯子和擬M?bius梯子的一些標(biāo)號.本文將研究擬梯子的(2,1)-全標(biāo)號問題。下面我們給出擬梯子的定義。

引理1.1[1]G是最大度為Δ≥2的圖，則λ(G)≥Δ+1。

圖1(a)

圖1(b)

圖2

圖3

圖4

圖5(a)

圖5(b)

圖6(a)

圖6(b)

圖7

圖8

圖9

2 P(t,n)的(2,1)-全標(biāo)號

由于擬梯子的(2,1)-全標(biāo)號即其剖分圖的L(2,1)-標(biāo)號。則從第1節(jié)的結(jié)果，可得擬梯子的(2,1)-全標(biāo)號數(shù)的結(jié)論。

定理2.1當(dāng)t=2a=4或5≤t=2a+1≤7時，λT(P(t,2))=4,λT(P(t,n))=5(n≥3)；當(dāng)t=2a≥6或t=2a+1≥9時，λT(P(t,n))=4。

[1] Griggs J R,Yeh R K.Labeling graphs with a condition at distance 2[J].SIAM J.Disc.Math,1992,5:586-595.

[2] Calamoneri T.The L(h,k)-labelling problem:a survey and annotated bibliography[J].Comput J,2006,49(5):585-608.

[3] Yeh R K.A survey on labeling graphs with a condition at distance two[J].Discrete Math，2006,306:1217-1231.

[4] Griggs J R,Jin X T.Recent progress in mathematics and engineering on optimal graph labellings with distance coditions[J].J Comb Optim，2007,14(2-3):249-257.

[5] Whittlesey M A,Georges J P，Mauro D W.On the lambda-number of Qnand related graphs[J].SIAM J.Discrete Math,1995,8:449-506.

[6] Havet F.(d,1)-total labeling of graphs[R].Workshop Graphs and Algorithms,Dijon(FRANCE),2003.

[7] Havet F,Yu M L.(d,1)-total labeling of graphs[R].Technical Report 4650,INRIA,2002.

[8] Wegner G.Graphs with given diameter and a coloring problem[R].Tech.Rep.University of Dortmund,Dortmund，1977.

[9] 杜娟,呂大梅,李冬冬,等.擬梯子的L(2,1)-標(biāo)號[J].遼寧大學(xué)學(xué)報：自然科學(xué)版，2013,4:308-313.

[10] 丁海燕,呂大梅,王金華,等.擬M?bius梯子的L(2,1)-標(biāo)號[J].遼寧大學(xué)學(xué)報：自然科學(xué)版，2014,4:293-299.

[11] 嚴冬梅,呂大梅.擬梯子的L(1,1)-標(biāo)號[J].遼寧大學(xué)學(xué)報：自然科學(xué)版，2015,4:296-300.

[12] 吳飛， 呂大梅.點接擬梯子的L(1,1)-標(biāo)號[J].遼寧大學(xué)學(xué)報：自然科學(xué)版，2016,1:1-6.

(責(zé)任編輯鄭綏乾)

The(2,1)-total-labelingsofthesimilarityladders

JIN Xin,DANG Xun-jiao,LV Da-mei*

(DepartmentofMathematics,NantongUniversity,Nantong226007，China)

An(2,1)-total-labeling of a graph is a functionffrom the vertex set and edge set to the set of all nonnegative integers such that the labels are different for two adjacent vertices,and for two adjacent edges,and the difference of the labels between a vertex and an edge which are incident is at least 2.In this paper,we study the(2,1)-total-labeling of the similarity ladders,and completely determine the(2,1)-total-labeling number of the similarity ladders.

L(2,1)-labeling;(2,1)-total-labeling;(2,1)-total-labeling number;similarity ladder

O 157.5

A

1000-5846(2017)04-0306-04

2017-08-10

國家自然科學(xué)基金(11371207);江蘇省自然科學(xué)青年基金(BK20140424);南通大學(xué)校級基金(14ZY009);南通大學(xué)大學(xué)生創(chuàng)新訓(xùn)練計劃項目(2017067)

金鑫(1988-)，男，研究生，教師，從事運籌學(xué)與控制論研究.

*

呂大梅(1976-)，女，副教授，從事運籌學(xué)與控制論.