基于廣播標號的魔幻圖關系

姚 明

(蘭州石化職業技術學院信息處理與控制工程學院)

基于廣播標號的魔幻圖關系

姚 明

(蘭州石化職業技術學院信息處理與控制工程學院)

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

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

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

1 (k(λ),μ)ml標號

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

設圖G有一個集合F(G)={G|G為二部分圖}，若對任意的圖H，T∈F，總有H∪T∈F；且任何一個圖G滿足G∈F；則稱F為圖G的二部圖空間。集合A的元素個數記為|A|。為方便敘述，整數集記為[m，n]={m，m+1，…，n}，其中n>m≥0。對于偶數l>k≥0，偶數集為[k,l]e={k,k+2,…,l}；對于奇數t>s≥1，奇數集是[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的一個標號h對任意的x,y∈V(G)，總有h∈Φ(G)={h|h(x)≠h(y)}，則h為正常標號；此外，若g∈Π(G)={g|g:V(G)∪E(G)→[m,n]}，且g∈Φ(G)，則g為圖G的一個正常的全標號。

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

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

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

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

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

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

定義3設集合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的任何一個優美標號滿足f∈L(G)。

則稱L(G)為G的二分優美空間，記為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的任何一個奇優美標號滿足f∈L(G)。

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

2 主要結果與證明

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

證明由于圖G∈F有一個λml，f∈Π(G),故存在常數λ，使圖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)-魔幻標號的充要條件是它有一個λ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)，則它有標號g∈Lb-odd(G)。

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

構造一個標號函數g滿足：

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

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

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

3 結束語

介紹(k(λ),μ)ml空間概念的定義和它可算法化的算法，使得C-圖與F-圖之間可通過橋L-圖相互轉化。結論有利于深入研究ROLG。后續工作將以研究f∈(k(λ),μ)ml與其他標號之間的關聯和(k(λ),μ)ml能否轉為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] 姚明，趙振學，姚兵.一類龍圖的廣義邊魔幻標號[J].甘肅科學學報，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)

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

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

TH865；O157.5

A

1000-3932(2017)11-1070-03

2017-06-12，

2017-09-14)