基于广播标号的魔幻图关系

姚 明

(兰州石化职业技术学院信息处理与控制工程学院)

基于广播标号的魔幻图关系

姚 明

(兰州石化职业技术学院信息处理与控制工程学院)

定义了(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)