立方路的多級距離數(shù)

郭紅芳，左連翠*

(天津師范大學數(shù)學科學學院，天津　300387)

立方路的多級距離數(shù)

郭紅芳，左連翠*

(天津師范大學數(shù)學科學學院，天津300387)

摘要：連通圖G的多級距離標號(電臺標號)是頂點集V(G)到非負整數(shù)集{0,1,2,…}的一個映射f，使得對于任意的u,v∈V(G)滿足：≥diam(G)+1-d(u,v)，其中diam(G)是圖G的直徑，d(u,v)表示兩點u,v之間的距離．映射f的跨度是指{f(u)-f(v)}．圖G的多級距離數(shù)是指圖G的所有多級距離標號的最小跨度．圖G的立方是由圖G通過在距離不超過3的任兩點間添加一條連邊構(gòu)成．本文給出了立方路的多級距離數(shù)．

關(guān)鍵詞：多級距離數(shù)；多級距離標號；有效頻道分配；最小跨度；立方路

0引言

多級距離標號又稱電臺標號，它是2-距離標號(L(2,1)-標號)的拓展．無論是L(2,1)-標號還是多級距離標號，都源于Hale的無線電頻道分配問題，它們都是特殊的染色問題．給定一個電臺的集合，一個有效的頻道分配是指這樣一個函數(shù)，它分配給每一個電臺一個頻道，使這些電臺之間的信號避免相互干擾．電臺之間相互干擾的度(級別)與電臺所處的位置有關(guān)，即兩電臺之間的距離越近，它們相互干擾的度就越大．因此為了避免這種干擾，距離越近的電臺，它們之間的頻道差就應該越大，從而頻道差由兩電臺之間的距離決定．為了模擬這個問題，圖論學家們構(gòu)造了一個圖，把每一個電臺表示成圖的一個頂點，每一對相鄰的電臺在圖中相應點之間連一邊．由此頻道分配問題即可轉(zhuǎn)化成圖的點染色問題．

圖G的多級距離數(shù)是指圖G的所有多級距離標號的最小跨度，記為r(G)．

圖G的立方，是指圖G通過在所有距離不超過3的兩個頂點之間添加一條連邊得到，記為G3．我們稱一條路(或圈)的立方為立方路(或立方圈)．隨著路和圈的多級距離數(shù)的完全解決，以及平方路的多級距離數(shù)被完全解決，我們考慮立方路的多級距離數(shù)，并得出下面的結(jié)論．

1主要定理的證明

本文用pn表示具有n個頂點的一條路，其中V(pn)={v1,v2,…,vn}和E(pn)={vivi+1:i=1,2,…,n-1},顯然

圖1　具有7個頂點的立方路

1.1下界

首先證明定理1中的下界．pn的中間頂點定義為路pn的中心．一條奇路p2k+1只有一個中心vk+1，而一條偶路p2k有兩個中心vk和vk+1，本文中取vk為偶路的中心．對于任意一個頂點u∈V(pn)，u的距離是指在pn中由u到pn的中心點的最短距離，記為L(u)．比如，設(shè)n=2k+1，則L(v1)=k,L(vk+1)=0，頂點序列A的距離記為L(A)．如果n=2k+1，則

如果n=2k，則

按如下方式定義左、右頂點集：如果n=2k+1，則左、右頂點集分別為{v1,v2,…,vk,vk+1}和{vk+1,vk+2,…,v2k,v2k+1}.

注意此時中心點vk+1既屬于左頂點集又屬于右頂點集．如果n=2k，則左、右頂點集分別為{v1,v2,…,vk-1,vk}和{vk+1,vk+2,…,v2k-1,v2k}.如果兩個點都屬于右(或左)頂點集，則稱它們在同一邊；否則，稱它們在不同邊．

把這n-1個不等式相加，得到

觀察上面的不等式可得：

(i)對每個i，有

等號成立當且僅當xi和xi+1在pn的不同邊，除非它們其中之一是中心點.

(ii)(2)式右邊的求和項中，L(x1)和L(xn)僅出現(xiàn)一次，其余各項均出現(xiàn)兩次．注意到

那么存在3m-1個i(1≤i≤6m-1)滿足

以及3m個i(1≤i≤6m-1)滿足

在上述排列中，當i(1≤i≤6m-1)為偶數(shù)時,有

當i(1≤i≤6m-1)為奇數(shù)時,有

另外，所有頂點中只有中心點的距離為0，從而

其中L(x1)=0,L(xn)=1.因此，由(1)式可得

2)當n=6m+1時，直徑k=2m，由于

與(1)式類似可得

其中L(x1)=0,L(xn)=1.因此由(1)式可得

3)當n=6m+2時，直徑k=2m+1.由于

其中L(x1)=0,L(xn)=1,因此由(1)式可得

4)當n=6m+3時，直徑k=2m+1.由于

其中L(x1)=0,L(xn)=1,故由(1)式得

5)當n=6m+4時，直徑k=2m+1.由于

其中L(x1)=0,L(xn)=1,結(jié)合(1)式可得

(6m2+11m+3)=6m2+7m+3.

6)當n=6m+5時，直徑k=2m+2.由于

其中L(x1)=0,L(xn)=1,故由(2)式得

1.2上界

只要給出跨度為上述值的多級距離標號，即可證明定理1．首先，證明下面的引理．

(3)

證明實際上，

設(shè)f是滿足上述假設(shè)的一個函數(shù)，只要證明：對任意的j≥i+2，有

對于i=1,2,…,n-1，設(shè)fi=f(xi+1)-f(xi)，則對于任意的j≥i+2，有

不妨設(shè)d1(xi,xi+1)≥d1(xi+1,xi+2)(對于d1(xi+1,xi+2)≥d1(xi,xi+1)的情況可以類似的證明)，則有d(xi,xi+1)≥d(xi+1,xi+2)，且

下面分情況進行討論．

1)假設(shè)j=i+2，設(shè)xi=va,xi+1=vb,xi+2=vc，只要考慮下面的情形：

( i )b

此時必有d(xi,xi+1)≤d(xi+1,xi+2)，但已知d(xi,xi+1)≥d(xi+1,xi+2)，所以

從而d1(xi,xi+1)<3,故d(xi,xi+2)=1，因此

( ii )a

那么

(iii)a

易知d(xi,xi+2)≥d(xi,xi+1)-d(xi+1,xi+2).當n≡2,3,4,5(mod6)時，易證

當n≡0,1(mod6)時，若

則有d(xi+1,xi+2)≤m，那么

若

則由(3)式得知d1(xi,xi+1)≡2(mod3)，因此

從而

2)假設(shè)j=i+3．

首先假設(shè)d(xi,xi+1),d(xi+1,xi+2),d(xi+2,xi+3)中至少有一對的和至多為2m+3，則

其次，假設(shè)d(xi,xi+1),d(xi+1,xi+2),d(xi+2,xi+3)中每一對的和都大于2m+3，則顯然有

(4)

設(shè)xi=va,xi+1=vb,xi+2=vc,xi+3=vd．由(4)式，一定有a

從而由(3)式可得

3)設(shè)j≥i+4．

顯然min{d1(xi,xi+1),d1(xi+1,xi+2)}≤φ(n),且對任意1≤i≤n-1，有fi=k+1-d(xi,xi+1)．

當n≡2,3,4(mod6)時，有

因此，

當n≡5(mod6)時，有

因此，

當n≡0,1(mod6)時，有

因此，

綜上所述，引理4得證．】

當m為奇數(shù)時，頂點排列如下：

當m為奇數(shù)時，頂點排列如下：

r(f)=6m2+7m+1.

當m為奇數(shù)時，頂點排列如下：

當m為奇數(shù)時，頂點排列如下：

綜上所述，定理1得證．

參考文獻:

[1]CHANGG,KEC,KUOD,etal．Ageneralizeddistancetwolabelingofgraphs[J].Disc Math,2000,220:57-66.

[2]CHANGG,KUOD.TheL(2,1)-labelingproblemongraphs[J].SIAM J Disc Math,1996,9:309-316.

[3]CHARTRANDG,ERWIND,HARARYF,etal.Radiolabelingsofgraphs[J].Bull Inst Combin Appl,2001,33:77-85.

[4]CHARTRANDG,ERWIND,ZHANGP.AgraphlabelingproblemsuggestedbyFMchannelrestrictions[J].Bull Inst Combin Appl,2005,43:43-57.

[5]GEORGESJ,MAUROD.Generalizedvertexlabelingswithaconditionatdistancetwo[J].Congr Numer,1995,109:141-159.

[6]GEORGESJ,MAUROD,STEINM.Labelingproductsofcompletegraphswithaconditionatdistancetwo[J].SIAM J Discrete Math,2001,14:28-35.

[7]GEORGESJ,MAUROD,WHITTLESEYM.Onthesizeofgraphslabeledwithaconditionatdistancetwo[J].J Graph Theory,1996,22:47-57.

[8]GEORGESJ,MAUROD,WHITTLESEYM.Relatingpathcoveringtovertexlabelingswithaconditionatdistancetwo[J].Disc Math,1994,135:103-111.

[9]GRIGGSJR,YEHRK.Labelinggraphswithaconditionatdistance2[J].SIAM J Disc Math,1992,5:586-595.

[10]CHARTRANDG,ERWIND,ZHANGP.Radioantipodalcoloringsofcycles[J].Congr Numer,2000,144:129-141.

[11]LIUD.Radio Number for Spiders[R].Manuscript,2004.

[12]LIUD,XIEM.Radio Number for Square Paths[R].Manuscript,2004.

[13]HALEWK.Frequencyassignment:theoryandapplications[J].Proc IEEE,1980,68:1497-1514.

[15]NIVENI,ZUCKERMANH,MONTGOMERYH.An Introduction to the Theory of Numbers[M].5thed.NewYork：JohnWileyandSonsInc,1991.

[16]GROSSJ,YELLENJ.Graph Theory and its Application[M].NewYork:CRCPress,1999.

[17]XIEM.Multiple Level Distance Labellings and Radio Number for Square Paths and Square Cycles[D].California:CaliforniaStateUniversity,2004.

[18]ZHAGNP.Radiolabellingsofcycles[J].Ars Combin,2002,65:21-32.

(責任編輯馬宇鴻)

*通訊聯(lián)系人，教授，博士，碩士研究生導師.主要研究方向為圖論及其應用.E-mail:lczuo@163.com

The multi-level distance number for cubic paths

GUO Hong-fang,ZUO Lian-cui

(College of Mathematical Science,Tianjin Normal University,Tianjin 300387,China)

Abstract:The multi-level distance labeling for a connected graph G,also called the radio labeling,is a mapping {0,1,2,…} such that for any u,v∈V(G)≥diam(G)+1-d(u,v),where diam(G) is the diameter of G,and d(u,v) denote the distance between u and v in G.The span of f is defined as {f(u)-f(v)}.The multi-level distance number of a graph G is the minimum span of all multi-level distance labeling for G.The cubic of G is a graph constructed from G by adding edges between vertices of distance at most three parts in G.In this paper,the multi-level distance number for the cubic path is obtained.

Key words:multi-level distance number;multi-level distance labeling;valid radio channel assignment;minimum span;cubic path

中圖分類號：O 157.5

文獻標志碼：A

文章編號：1001-988Ⅹ(2015)02-0012-07

作者簡介：郭紅芳(1990—)，女，河北臨漳人，碩士研究生.主要研究方向為圖論及其應用.E-mail:ghfkeji@126.com

基金項目:國家自然科學青年基金資助項目(61103073)

收稿日期：2014-03-12;修改稿收到日期:2014-07-13