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

金 鑫，黨雪嬌，呂大梅

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

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

金 鑫，黨雪嬌，呂大梅*

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

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

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

0 引言

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

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

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

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

文獻(xiàn)[8-11]研究了擬梯子和擬M?bius梯子的一些標(biāo)號(hào).本文將研究擬梯子的(2,1)-全標(biāo)號(hà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)號(hào)

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

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

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

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

[12] 吳飛， 呂大梅.點(diǎn)接擬梯子的L(1,1)-標(biāo)號(hào)[J].遼寧大學(xué)學(xué)報(bào)：自然科學(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é)校級(jí)基金(14ZY009);南通大學(xué)大學(xué)生創(chuàng)新訓(xùn)練計(jì)劃項(xiàng)目(2017067)

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

*

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