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

金 鑫，黨雪嬌，呂大梅

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

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

金 鑫，黨雪嬌，呂大梅*

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

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

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

0 引言

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

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

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

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

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

引理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)-全標號

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

定理2.1當t=2a=4或5≤t=2a+1≤7時，λT(P(t,2))=4,λT(P(t,n))=5(n≥3)；當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)-標號[J].遼寧大學(xué)學(xué)報：自然科學(xué)版，2013,4:308-313.

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

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

[12] 吳飛， 呂大梅.點接擬梯子的L(1,1)-標號[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é)與控制論.