Cartesian積的局部邊-路替換圖的 L(2,1)-標號

杜 娟，呂大梅, 張 科

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

?

Cartesian積的局部邊-路替換圖的 L(2,1)-標號

杜 娟，呂大梅, 張 科

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

設(shè)d為正整數(shù)，圖G的一個L(d,1)-標號就是從非負整數(shù)集到V(G)的一個函數(shù)，且使得2個相鄰頂點的標號相差至少是d，2個距離為2的頂點的標號相差至少為1. 圖G的L(d,1)-標號的跨度就是所有L(d,1)-標號的最大值和最小值之差. 圖G的L(d,1)-標號數(shù)是G的所有L(d,1)-標號下跨度的最小值. 在已有研究圖G的邊-路替換圖的L(d,1)-標號基礎(chǔ)上，研究了Cartesian積的局部邊-路替換圖的L(2,1)-標號.

頻道分配；L(d,1)-標號；Cartesian積；局部邊-路替換圖

在頻道分配問題上，需要將各個頻率分配到各電臺，如果2個距離很近的電臺用接近的頻率發(fā)送信息就會相互影響. 為了避免此類情況發(fā)生，其頻率分配必須有足夠大的距離. 而且，如果2個距離相近但不是很近的電臺，分配的頻率也必須不同. 此問題就是圖G的距離2標號問題.

設(shè)d為正整數(shù)，圖G的一個L(d,1)-標號就是從非負整數(shù)集到V(G)的一個函數(shù)，且使得2個相鄰頂點的標號相差至少是d，2個相距為2的頂點的標號相差至少是1. 圖G的L(d,1)-標號的跨度就是所有L(d,1)-標號的最大值和最小值之差. 圖G的L(d,1)-標號數(shù)是G的所有L(d,1)-標號下跨度的最小值，用λd(G)表示.

1992年，文獻 [1]提出L(2,1)-標號的概念，并猜想：當Δ≥2時，對任何圖G，有λ(G)≤Δ2，其中Δ是圖G的最大度. 此概念已被廣泛研究，并延伸出許多具有挑戰(zhàn)性的問題[2-12]. 在文獻[13-14]的基礎(chǔ)上，筆者研究了圖G的邊-路替換圖G(Pk)(即用路Pk代替圖G中的每條邊所得的圖)的L(d,1)-標號.

下文將研究k和l中一個等于2、另一個大于2的條件下Cartesian積的局部邊-路替換圖的L(2,1)-標號. 首先給出幾個相關(guān)定義.

圖G=(V，E)和H=(W，F(xiàn))的Cartesian積G□H定義如下：

V(G□H)=V×W且E(G□H)={{(u,x),(v,y)}:u=v且(x,y)∈F，或者，x=y且(u,v)∈

E}=E1∪E2，其中，E1={{(u,x),(v,y)}:u=v且(x,y)∈F}，E2={{(u,x),(v,y)}:x=y且(u,v)∈E}.

假設(shè)G和H是2個連通圖，分別有m和n個頂點.方便起見，將圖G□H的頂點看作在二維歐氏空間中的點. G□H中的每一個點都用坐標(a,b)來表示，其中a,b均為非負整數(shù)，且0≤a≤m-1,0≤b≤n-1. 對v=(a,b)∈V(G□H)， v是G□H第a行第b列的頂點，也是(G□H)(Pk,Pl)第a行第b列的節(jié)點.

由于(G□H)(P2,Pl)同構(gòu)于(H□G)(Pl,P2)，故接下來研究在k≥3且l=2的條件下局部邊-路替換圖(G□H)(Pk,Pl)的L(2,1)-標號. 首先給出2個引理.

引理1[1]設(shè)G是最大度為Δ≥2的圖，則λ(G)≥Δ+1.

引理2[1]設(shè)G是最大度為Δ≥2的圖，若G包含3個度為Δ的頂點,且其中一個頂點與另外2個相鄰，則λ(G)≥Δ+2.

由引理1, 下界是顯而易見的：

λ((G□H)(Pk,P2))≥Δ+1.

對特殊的Δ1=1且Δ2=1，有

G□H?P2□P2，且(P2□P2)(Pk,P2)?C2k.

因此，

λ((P2□P2)(Pk,P2))=4.

下面研究Δ1,Δ2中至少1個大于等于2的情形.方便起見，設(shè)λ1=λ(G(Pk))，λ2=λ(H).

1 Δ1=1，Δ2≥2

定理1 設(shè)Δ2≥2且H不是頂點數(shù)小于5的路.

當k≥6，λ((P2□H)(Pk,P2))≤λ2+1；

當3≤k≤5，λ((P2□H)(Pk,P2))≤λ2+2.

情形1 k≡0(mod 3)且k≠3. 當0≤x≤λ2-1時，如果x≠0,2,則替換路的標號為x(λ2+1)02402(λ2+1)x，否則為x(λ2+1)13513(λ2+1)x；當x=λ2時，用λ2+1替換節(jié)點(0, j)和(1, j)的標號λ2，并將替換路標為(λ2+1)(λ2-1)02402(λ2-1)(λ2+1)(λ2≥5)，(λ2+1)(λ2-1)04251(λ2-1)(λ2+1)(λ2=4).

情形2 k≡1(mod 3)且k≠4. 當0≤x≤λ2-1時，若x≠0,2,則把替換路標為x(λ2+1)240(λ2+1)x，否則標為0(λ2+1)142(λ2+1)0，2(λ2+1)130(λ2+1)2；當x=λ2時，用λ2+1替換節(jié)點(0, j)和(1, j)的標號λ2，并且把替換路標為(λ2+1)(λ2-1)130(λ2-1)(λ2+1)(λ2≥5)，(λ2+1)(λ2-1)140(λ2-1)(λ2+1)(λ2=4).

情形3 k≡2(mod 3)且k≠5. 當0≤x≤λ2-1時，如果x≠2,3,則把替換路標為x(λ2+1)2403(λ2+1)x，否則標為x((λ2+1))1420((λ2+1))x；當x=λ2時，用λ2+1替換節(jié)點(0, j)和(1, j)的標號λ2，并且把替換路標為(λ2+1)(λ2-1)0240(λ2-1)(λ2+1)(λ2≠5)，(λ2+1)(λ2-1)0250(λ2-1)(λ2+1)(λ2=5).

情形4 k=5.當0≤x≤λ2-2時，如果x≠0,則把替換路標為x(λ2+1)0λ2x，否則標為0(λ2+1)1λ20；當x=λ2時，用λ2+2替換節(jié)點(1,j)的標號λ2，并且把替換路標為(λ2+2)λ21(λ2-1)(λ2+2).當x=λ2-1時，替換路標為(λ2-1)(λ2+1)1(λ2+2)(λ2-1).

情形5 k=4.當x≠0，替換路標為x(λ2+2)0(x+1)，否則標為0p(λ2+2)1，其中p為節(jié)點0的鄰點中未出現(xiàn)的標號.

情形6 k=3.若λ2為奇，替換路標為x(λ2+2)(λ2-x)；若λ2為偶，當x≠0時，替換路標為x(λ2+2)(λ2+1-x)，x=0時,標為0p(λ2+1)，其中p為節(jié)點0的鄰點中未出現(xiàn)的標號，且當p=λ2時，改為0λ2(λ2+2).

綜合以上情形，定理1得證.

2 Δ1≥2，Δ2≥2

定理2 設(shè)Δ1≥2，Δ2≥2.則當k≥8時，有λ((G□H)(Pk,P2))≤λ2+Δ1.

證明 首先給出(G□H)(Pk,P2)第0行跨度為λ2的L(2,1)-標號. 當ki≥8，i=1,2,…,s時，置(G□H)(Pk,P2)的其余行標號與(G□H)(Pk,P2)的第0行相同. 假設(shè)節(jié)點標號為x. 當0≤x≤λ2-2時，此節(jié)點在替換路上的鄰點用[λ2,λ2+Δ1-1]里的標號來標示，當x=λ2-1時，則此節(jié)點在替換路上的鄰點用[λ2+1,λ2+Δ1]里的標號來標示，當x=λ2時，則用λ1+Δ2替換該節(jié)點的標號λ2，且該節(jié)點在替換路上的鄰點用[λ2-1,λ2+Δ1-2]里的標號來標示. 由于Δ2≥2，λ2≥3，λ2+Δ1≥5，進而每一列的替換路都可在[0,λ2+Δ1]中被標號，abc表示重復(fù)結(jié)構(gòu)，其中，p,q∈[λ2,λ2+Δ1-1]，a,b∈[λ2+1,λ2+Δ1]，r,s∈[λ2-1,λ2+Δ1-2]，具體如下：

情形1 k≡0(mod 3)且k≠3,6.

當x=λ2時，替換路標為

情形2 k≡1(mod 3)且k≠4,7.

當1≤x≤λ2-1時，替換路標為

當x=λ2時，替換路標為

情形3 k≡2(mod 3)且k≠5.

當x=λ2時，替換路標為

因此，當k≥8時，有

λ((G□H)(Pk,P2))≤λ2+Δ1.

類似可得如下結(jié)論.

定理3 假設(shè)Δ1≥2，Δ2≥2. 如果k≥6，那么λ((G□H)(P2,Pk))≤λ1+Δ2.

推論1 假設(shè)Δ1≥2，Δ2≥2. 如果k≥6，那么λ((G□H)(P2,Pk))≤min{λ1+Δ2,λ2+Δ1}.

3 Δ1≥2,Δ2=1

定理4 假設(shè)Δ1≥2,Δ2=1(即H為路P2). 則當k≥6時，有λ((G□P2)(Pk,P2))≤λ1+2.

證明 給出(G□H)(Pk,P2)在0列的跨度為λ1的L(2,1)-標號f. 另一列標號為f+2. 如果在第0列的節(jié)點與對應(yīng)第1列節(jié)點的鄰點標號相同，將此第1列節(jié)點的鄰點標號改為0；如果在第1列的節(jié)點與對應(yīng)第0列節(jié)點的鄰點標號相同，將此第0列節(jié)點的鄰點標號改為 λ1+2. 則得到了(G□H)(Pk,P2)(k≥6)跨度為λ1+2的L(2,1)-標號，因此，λ((G□P2)(Pk,P2))≤λ1+2.

[1] GRIGGS J R, YEH R K. Labeling graphs with a condition at distance two[J]. Discrete Mathematics,1992(5):586-595.

[2] WHITTLESEY M A, GEORGES J P,MAURO D W. On theλ-number ofQnand related graphs[J]. Discrete Mathematics,1995(8):449-506.

[3] JHA P K, KLAZAR S, VESEL A. OptimalL(d,1)-labelings of certain directed products of cycles and Cartesian products of cycles[J]. Discrete Applied Mathematics,2005,152:257-265.

[4] JHA P K, NARAYANAN A, SOOD P, et al. OnL(2,1)-labeling of the Cartesian product of a cycle and a path[J]. Ars Combin,2000,55:81-89.

[5] JHA P K. OptimalL(2,1)-labelings of strong Cartesian products of cycles [J].Theory and Appl,2001,48:498-500.

[6] JHA P K, KLAZAR S,VESEl A.L(2,1)-labeling of direct products of pathes and cycles[J]. Discrete Applied Mathematics,2005,145:317-325.

[7] KUO D, YAN J H. OnL(2,1)-labeling of Cartesian products of pathes and cycles[J].Discrete Math,2004,238:137-144.

[8] JHA P K. OptimalL(2,1)-labeling of Cartesian products of cycles, with an application to independent domination, IEEE Trans Circ Syst-I:Fund[J]. Theory and Appl,2000,147:1531-1534.

[9] GEORGES J P, MAURO D W, STEIN M I. Labeling products of complete graphs with a conditionat distance two[J]. SIAM J Discrete Math,2000,14:28-35.

[10] ERWIN D J, GEORGES J P, MAURO D W. On labeling the vertices of products of complete graphs with distance constraints[J].Naval Research Logistics,2005,52(2):138-141.

[12] SCHWARZ C, TROXELL D.L(2,1)-labeling of Cartesian products of two cycles[J].Discrete Appl Math,2006,154：1522-1540.

[13] LYU D M.L(2,1)-labelings of the edge-path-replacement of a graph[J]. J Comb Optim,2013,26(4):385-392.

[14] LYU D M, LIN N F.L(d,1)-labelings of the edge-path-replacement of a graph[J]. J Comb Optim,2013,26:819-831.

DU Juan, LYU Damei, ZHANG Ke

(SchoolofScience,NantongUniversity,Nantong226007,JiangsuProvince,China)

L(2,1)-labelings of the local-edge-path-replacements of Cartesian products. Journal of Zhejiang University(Science Edition), 2016,43(6):679-681

For a positive integerd, anL(d,1)-labeling of a graphGis an assignment of nonnegative integers to the vertices ofV(G) such that the difference between labels of adjacent vertices is at leastd, and the difference between labels of vertices whose distance are two aparts is at least 1. The span of anL(d,1)-labeling of a graphGis the difference between the maximum and minimum integers of all labels. TheL(d,1)-labeling-number ofGis the minimum span over allL(d,1)-labelings ofG. Based on the work ofL(d,1)-labels of the edge-path-replacement of a graphG, we study theL(2,1)-labeling of the local-edge-path-replacements of the Cartesian products.

channel assignment;L(d,1)-labeling; Cartesian product; local edge-path-replacement

2014-06-06.

國家自然科學基金資助項目(11371207)；江蘇省青年基金項目(BK20140424)；南通大學自然科學基金資助項目(14ZY009).

杜 娟(1976-)，ORCID:http://orcid:org/0000-0002-0424-0998,女，碩士，講師，主要從事圖論及其應(yīng)用研究,E-mail：djalarm@ntu.edu.cn.

10.3785/j.issn.1008-9497.2016.06.010

O 157.5

A

1008-9497(2016)06-679-03