擬m?bius梯子的(1,1)-全標號

蔡漢橋，陳 潔，呂大梅

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

擬m?bius梯子的(1,1)-全標號

蔡漢橋，陳 潔，呂大梅*

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

圖的(1,1)-全標號是從點集及邊集到非負整數(shù)集的一個函數(shù)f，且滿足：任兩相鄰頂點標號相異；任兩相鄰邊標號相異；及任關聯(lián)的點和邊標號也相異.本文對擬m?bius梯子的(1,1)-全標號進行研究,確定了擬m?bius梯子的(1,1)-全標號數(shù).

L(1,1)-標號;L(1,1)-標號數(shù);擬m?bius梯子

0 引言

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

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

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

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

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

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

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

圖1

圖2

圖3

圖4

圖5

圖6

2 M(t,n)的(1,1)-全標號

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

定理2.1當t≥6時，λ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)-標號[J].遼寧大學學報：自然科學版,2013,4:308-313.

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

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

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

(責任編輯鄭綏乾)

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

國家自然科學基金(11371207),江蘇省自然科學青年基金(BK20140424)，南通大學校級基金(14ZY009),南通大學大學生創(chuàng)新訓練計劃項目(2017059)

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

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