蔡漢橋，陳 潔，呂大梅

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

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

蔡漢橋，陳 潔，呂大梅*

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

圖的(1,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)也相異.本文對(duì)擬m?bius梯子的(1,1)-全標(biāo)號(hào)進(jìn)行研究,確定了擬m?bius梯子的(1,1)-全標(biāo)號(hào)數(shù).

L(1,1)-標(biāo)號(hào);L(1,1)-標(biāo)號(hào)數(shù);擬m?bius梯子

0 引言

圖的距離2標(biāo)號(hào)問題是無線電通信波段分配問題的圖論模式。Griggs和Robert[1]在此問題的基礎(chǔ)上，提出圖的L(2,1)-標(biāo)號(hào)概念,并推廣為L(zhǎng)(h,k)-標(biāo)號(hào)問題。之前，Robort[2]把h=1,k=1情形即L(1,1)-標(biāo)號(hào)，作為組合分配問題進(jìn)行研究。關(guān)于L(1,1)-標(biāo)號(hào)的研究,參見綜述[4-6].

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

1995年，Whittlesty[3]等人研究了一個(gè)很有趣的問題——剖分圖的L(2,1)-標(biāo)號(hào)。2002年，Havet和Yu[7-8]把G的剖分圖的L(2,1)-標(biāo)號(hào)稱為G的(2,1)-全標(biāo)號(hào)，并推廣研究了(d,1)-全標(biāo)號(hào)概念。接下來我們先給出(1,1)-全標(biāo)號(hào)的定義。

一個(gè)圖G的(1,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所有(1,1)-全標(biāo)號(hào)下的跨度max{f(v);v∈V(G)∪E(G)}的最小值為圖G的(1,1)-全標(biāo)號(hào)數(shù)，記為λT(G)。

文獻(xiàn)[9-12]對(duì)擬梯子和擬M?bius梯子的L(1,1)和L(2,1)-標(biāo)號(hào)進(jìn)行了研究.本文將研究擬M?bius梯子的(1,1)-全標(biāo)號(hào)。下面我們給出擬M?bius梯子的定義。

由于擬M?bius梯子的(1,1)-全標(biāo)號(hào)即其剖分圖的L(1,1)-標(biāo)號(hào)。因此本文第1節(jié)中，我們先研究擬M?bius梯子的剖分圖的L(1,1)-標(biāo)號(hào)；而第2節(jié)則是在第1節(jié)結(jié)果基礎(chǔ)上，給出擬M?bius梯子的(1,1)-全標(biāo)號(hào)數(shù)。

引理1.1[5]設(shè)G是最大度為Δ≥2的圖，λ(G)≥Δ。

圖1

圖2

圖3

圖4

圖5

圖6

2 M(t,n)的(1,1)-全標(biāo)號(hào)

由于擬M?bius梯子的(1,1)-全標(biāo)號(hào)即其剖分圖的L(1,1)-標(biāo)號(hào)。從而由第1節(jié)，擬M?bius梯子的(1,1)-全標(biāo)號(hào)數(shù)的結(jié)論如下。

定理2.1當(dāng)t≥6時(shí)，λT(M(t,n))=Δ=3。

[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] Borodin O V,Kostochka A V，Woodall D R.Total colorings of planar graphs with large maximum degree[J].J.Graph Theory,1996,26:53-59.

[3] Whittlesey M A,Georges J P,Mauro D W.On the lambda-number of Q_{n} and related graphs[J].SIAM J.Discrete Math,1995,8:449-506.

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

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

[6] 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.

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

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

[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(1,1)-total-labelingsoftheSimilarityM?biusLadders

CAI Han-qiao,CHEN Jie,LV Da-mei

(Departmentofmathematics,NantongUniversity,Nantong226007,China)

An(1,1)-total-labeling of a graph is a function f from the vertex set and edge set to the set of all nonnegative integers such that the labels are different for two adjacent vertices,two adjacent edges,and for a vertex and an edge which are incident.In this paper,we study the (1,1)-total-labeling of the similarity m?bius ladders,and determine the (1,1)-total-labeling number of the similarity m?bius ladders.

L(1，1)-labeling;L(1，1)-labeling number;similarity m?bius ladder

O 157.5

A

1000-5846(2017)04-0302-04

2017-08-02

國(guó)家自然科學(xué)基金(11371207),江蘇省自然科學(xué)青年基金(BK20140424)，南通大學(xué)校級(jí)基金(14ZY009),南通大學(xué)大學(xué)生創(chuàng)新訓(xùn)練計(jì)劃項(xiàng)目(2017059)

蔡漢橋(1986-),女,研究生,教師,從事運(yùn)籌學(xué)與控制論研究.

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