杜 娟，呂大梅, 張 科

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

?

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

杜 娟，呂大梅, 張 科

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

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

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

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

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

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

下文將研究k和l中一個等于2、另一個大于2的條件下Cartesian積的局部邊-路替換圖的L(2,1)-標(biāo)號. 首先給出幾個相關(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中的每一個點都用坐標(biāo)(a,b)來表示，其中a,b均為非負(fù)整數(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)-標(biāo)號. 首先給出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的路.

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

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

情形1 k≡0(mod 3)且k≠3. 當(dāng)0≤x≤λ2-1時，如果x≠0,2,則替換路的標(biāo)號為x(λ2+1)02402(λ2+1)x，否則為x(λ2+1)13513(λ2+1)x；當(dāng)x=λ2時，用λ2+1替換節(jié)點(0, j)和(1, j)的標(biāo)號λ2，并將替換路標(biāo)為(λ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. 當(dāng)0≤x≤λ2-1時，若x≠0,2,則把替換路標(biāo)為x(λ2+1)240(λ2+1)x，否則標(biāo)為0(λ2+1)142(λ2+1)0，2(λ2+1)130(λ2+1)2；當(dāng)x=λ2時，用λ2+1替換節(jié)點(0, j)和(1, j)的標(biāo)號λ2，并且把替換路標(biāo)為(λ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. 當(dāng)0≤x≤λ2-1時，如果x≠2,3,則把替換路標(biāo)為x(λ2+1)2403(λ2+1)x，否則標(biāo)為x((λ2+1))1420((λ2+1))x；當(dāng)x=λ2時，用λ2+1替換節(jié)點(0, j)和(1, j)的標(biāo)號λ2，并且把替換路標(biāo)為(λ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.當(dāng)0≤x≤λ2-2時，如果x≠0,則把替換路標(biāo)為x(λ2+1)0λ2x，否則標(biāo)為0(λ2+1)1λ20；當(dāng)x=λ2時，用λ2+2替換節(jié)點(1,j)的標(biāo)號λ2，并且把替換路標(biāo)為(λ2+2)λ21(λ2-1)(λ2+2).當(dāng)x=λ2-1時，替換路標(biāo)為(λ2-1)(λ2+1)1(λ2+2)(λ2-1).

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

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

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

2 Δ1≥2，Δ2≥2

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

證明 首先給出(G□H)(Pk,P2)第0行跨度為λ2的L(2,1)-標(biāo)號. 當(dāng)ki≥8，i=1,2,…,s時，置(G□H)(Pk,P2)的其余行標(biāo)號與(G□H)(Pk,P2)的第0行相同. 假設(shè)節(jié)點標(biāo)號為x. 當(dāng)0≤x≤λ2-2時，此節(jié)點在替換路上的鄰點用[λ2,λ2+Δ1-1]里的標(biāo)號來標(biāo)示，當(dāng)x=λ2-1時，則此節(jié)點在替換路上的鄰點用[λ2+1,λ2+Δ1]里的標(biāo)號來標(biāo)示，當(dāng)x=λ2時，則用λ1+Δ2替換該節(jié)點的標(biāo)號λ2，且該節(jié)點在替換路上的鄰點用[λ2-1,λ2+Δ1-2]里的標(biāo)號來標(biāo)示. 由于Δ2≥2，λ2≥3，λ2+Δ1≥5，進(jìn)而每一列的替換路都可在[0,λ2+Δ1]中被標(biāo)號，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.

當(dāng)x=λ2時，替換路標(biāo)為

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

當(dāng)1≤x≤λ2-1時，替換路標(biāo)為

當(dāng)x=λ2時，替換路標(biāo)為

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

當(dāng)x=λ2時，替換路標(biāo)為

因此，當(dāng)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). 則當(dāng)k≥6時，有λ((G□P2)(Pk,P2))≤λ1+2.

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

國家自然科學(xué)基金資助項目(11371207)；江蘇省青年基金項目(BK20140424)；南通大學(xué)自然科學(xué)基金資助項目(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