基于廣播標(biāo)號的魔幻圖關(guān)系

姚 明

(蘭州石化職業(yè)技術(shù)學(xué)院信息處理與控制工程學(xué)院)

基于廣播標(biāo)號的魔幻圖關(guān)系

姚 明

(蘭州石化職業(yè)技術(shù)學(xué)院信息處理與控制工程學(xué)院)

定義了(k(λ),μ)ml，它使得標(biāo)定的圖的邊滿足標(biāo)號。利用魔幻圖的關(guān)系，證得每一個C-圖具有(k(λ),μ)ml，證明過程可算法化，得到標(biāo)號之間可互化的結(jié)果。

ROLG ASRC (k(λ),μ)mlLb-g(G)Lb-odd(G)

為了有效規(guī)范分配無線電頻道(Assigning Radio Channels，ASRC)，使各個基站之間分配一個合適的頻率以便互不干擾， Chartrand等提出廣播標(biāo)號(Radio Labeling，ROLG)的概念?；ゲ桓蓴_的問題可以抽象為依據(jù)各項頂點之間距離的圖的標(biāo)號問題，不同距離的頂點之間的干擾與其距離有關(guān)，已知圖標(biāo)號中的許多問題是困難問題[1]。由于ROLG有著良好的應(yīng)用前景，近年來發(fā)展很快，文獻(xiàn)[2]對Caterpillar圖(簡稱C-圖)與Firecracker圖(簡稱F-圖)進(jìn)行了研究，目前的研究成果大都是一些簡單圖，或是給出了圖的上下界。 筆者的研究表明有λml的C-圖與有(k(λ),μ)ml的Lobster圖(以下簡稱L-圖)之間存在著關(guān)聯(lián)，認(rèn)為F-圖是L-圖的特例；證明過程可算法化，它不僅有理論意義，還可以為實際應(yīng)用提供較好的算法，可顯著改變ROLG的研究限于特殊圖類的情形，為進(jìn)一步研究ASRC問題提供了數(shù)理支撐。

1 (k(λ),μ)ml標(biāo)號

若無特別聲明，文中論及的圖均指有限、無向、簡單圖，沒有定義的術(shù)語和符號均參見文獻(xiàn)[3]。

設(shè)圖G有一個集合F(G)={G|G為二部分圖}，若對任意的圖H，T∈F，總有H∪T∈F；且任何一個圖G滿足G∈F；則稱F為圖G的二部圖空間。集合A的元素個數(shù)記為|A|。為方便敘述，整數(shù)集記為[m，n]={m，m+1，…，n}，其中n>m≥0。對于偶數(shù)l>k≥0，偶數(shù)集為[k,l]e={k,k+2,…,l}；對于奇數(shù)t>s≥1，奇數(shù)集是[s,t]°={s,s+2,s+4,…,t}。

記圖G的頂點集為f(V(G))={f(x)|x∈V(G)}、邊集為f(E(G))={f(xy)|xy∈E(G)}。如果圖G∈F的一個標(biāo)號h對任意的x,y∈V(G)，總有h∈Φ(G)={h|h(x)≠h(y)}，則h為正常標(biāo)號；此外，若g∈Π(G)={g|g:V(G)∪E(G)→[m,n]}，且g∈Φ(G)，則g為圖G的一個正常的全標(biāo)號。

度為1的頂點稱為葉子，一個圖G的所有葉子集合記為L(G)，葉子數(shù)為|L(G)|。如果刪除一棵樹G所有葉子，余圖G-L(G)是一條路，則稱圖G為C-圖;如果刪除一棵樹G所有葉子，余圖G-L(G)是C-圖，則稱樹G為L-圖[4，5]。

定義1設(shè)連通圖G∈F有一個正常的全標(biāo)號f∈Π(G)，若存在常數(shù)λ，使得圖G的每條邊uv∈E(G)滿足f(u)+f(v)+f(uv)=λ，則稱f為G的λ-魔幻標(biāo)號(λ-magic labelling，λml)[6，7]。

定義2設(shè)連通圖G∈F的邊集合是兩個不交的邊子集E(H)、E(T)的并。如果圖H有一個正常的全標(biāo)號f∈Π(G)，滿足：

a. 存在常數(shù)λ與k，使得對每條邊uv∈E(H)、每一個s∈L(H)，有f(u)+f(v)+f(uv)=λ與f(s)+f(sv)=k成立；

b. 每條邊xy∈E(T)有一個導(dǎo)出的號f*(x)+f*(xy)=f(u)+f(uv)成立；

c.f*(E(T))+f(E(H))=q，則稱f為H的(k(λ),μ)-魔幻標(biāo)號((k(λ),μ)-magic labelling，(k(λ),μ)ml)。

定義3設(shè)集合L(G)={f|f:V(G)→[0,p-1],G∈F}，若：

a. 對任意的f∈L(G)，使得uv∈E(G),滿足{f(uv)|uv∈E(G)}=[1,q];

b. 圖G的任何一個優(yōu)美標(biāo)號滿足f∈L(G)。

則稱L(G)為G的二分優(yōu)美空間，記為Lb-g(G)[8]。

定義4如果集合L(G)={f|f:V(G)→[0,2p-3],G∈F}，滿足：

a. 對任意的f∈L(G)，使得uv∈E(G),滿足{f(uv)|uv∈E(G)}=[0,2p-3]°；

b. 圖G的任何一個奇優(yōu)美標(biāo)號滿足f∈L(G)。

則稱L(G)為G的二分奇優(yōu)美空間，記為Lb-odd(G)[8]。

2 主要結(jié)果與證明

定理1令N為全體整數(shù)集合。如果圖G∈F有一個λml,f∈Π(G)，總存在任意數(shù)對(s,t)(s,t∈N)，使得對每條邊uv∈E(G)有f(u)+f(v)=s+tf(uv)成立。

證明由于圖G∈F有一個λml，f∈Π(G),故存在常數(shù)λ，使圖G的每條邊uv∈E(G)，滿足：

f(u)+f(v)+f(uv)=λ

因此有：

f(u)+f(v)=λ-f(uv)

圖1為λml圖。由定理1易得引理2。

圖1 λml圖

引理2圖G∈F有一個(λ,-1)-魔幻標(biāo)號的充要條件是它有一個λml。

定理3如果圖G∈F有一個(k(λ),μ)ml，則μ=k+λ。

證明由定義2可知，圖G∈F的邊集合為E(G)=E(H)∪E(T)，對每條邊uv∈E(H)，每一個s∈L(H)，有f(u)+f(v)+f(uv)=λ與f(s)+f(sv)=k。

(k(λ),μ)ml圖如圖2所示。

圖2 (k(λ),μ)ml圖

定理4如果圖G∈F有一個λml,f∈Π(G)，則它有標(biāo)號g∈Lb-odd(G)。

證明由定義1可知，圖G∈F有標(biāo)號f，使得對每條邊uv∈E(G)，有f(u)+f(v)+f(uv)=λ。

構(gòu)造一個標(biāo)號函數(shù)g滿足：

綜合a、b，有φ(E(Ω))={1,3,…,2p-3}，所以g∈Lb-odd(G)。

定理5如果圖G∈F有一個(k(λ),μ)ml,f∈Π(G)，則它有對偶標(biāo)號g。

證明由定義2可知，圖G∈F有一個(k(λ),μ)ml，構(gòu)造一個標(biāo)號函數(shù)g滿足：

3 結(jié)束語

介紹(k(λ),μ)ml空間概念的定義和它可算法化的算法，使得C-圖與F-圖之間可通過橋L-圖相互轉(zhuǎn)化。結(jié)論有利于深入研究ROLG。后續(xù)工作將以研究f∈(k(λ),μ)ml與其他標(biāo)號之間的關(guān)聯(lián)和(k(λ),μ)ml能否轉(zhuǎn)為ROLG為重點。

[1] Gallian J A.A Dynamic Survey of Graph Labelling[J].The Electronic Journal of Combinatorics,2012,(14):#DS6.

[2] Devsi B.Radio Number of Trees[J].Electronic Notes in Discrete Mathematics,2015,48:135～141.

[3] Bondy J A,Murty U S R.Graph Theory with Application[M].New York:MaCmillan,1976.

[4] Zhou X Q.Every Lobster is Odd-elegant[J].Information Processing Letters,2013,(113):30～33.

[5] Zhou X Q,Yao B.A Proof to the Odd-gracefulness of All Lobsters[J].Ars Combinatoria,2012,103:13～18.

[6] Kotzig A,Rosa A.Magic Valuations of Finite Graphs[J].Canada Math Bull,1970,(13):451～461.

[7] Yao B,Zhang Z F,Yao M,et al.A New Type of Magical Coloring[J].Advances in Mathmatics,2008,(37):571～583.

[8] 姚明，趙振學(xué)，姚兵.一類龍圖的廣義邊魔幻標(biāo)號[J].甘肅科學(xué)學(xué)報，2016，28(3)：1～5.

MagicalGraphsRelationBasedonRadioLabelling

YAO Ming

(CollegeofInformationProcessingandControlEngineering,LanzhouPetrochemicalcollegeofVocationalTechnology)

A new graph labelling called (k(λ),μ)ml magical labelling was defined. Through making use of close relationship between caterpillars and lobsters, “every lobster admitting an (k(λ),μ)ml magical labelling” was proved to be transformed into the algorithm and the conclusion that labellings can be interchanged was reached.

ROLG, ASRC,(k(λ),μ)ml,Lb-g(G)，Lb-odd(G)

國家自然科學(xué)基金項目(61163054)；甘肅省財政廳專項資金(2014-63)；甘肅省高等學(xué)校研究生導(dǎo)師科研項目(1216-01)。

姚明(1962-),教授，從事圖的著色和標(biāo)號及計算優(yōu)化的研究，yybm918@163.com。

TH865；O157.5

A

1000-3932(2017)11-1070-03

2017-06-12，

2017-09-14)