关于L图的运算研究

姚明 姚兵

摘要：定義图与标号，给出标号的可算法化的算法，得到大规模快速地构造图的方法，为快速大规模构造图形和方便实际应用在理论上有了依据。

关键词：asrc;rolg;;graphs;;;stl;

中图分类号：O157.5 文献标识码：A 文章编号：1007-9416（2020）01-0100-02

1 预备知识

应对无线电频道分配（assigning radio channels，asrc）互不干扰问题的广播标号（radio labeling， rolg）基于简单图给出了各种研究成果，但各基站之间的关联以及标定标号的结论多因所设条件计算复杂较难实际应用[1-2]。本文定义了就研究rolg方面有代表性的图并给出了可算法化的构造过程，给出了魔幻广播标号，较细地探讨了对rolg影响较深的性质，从而使rolg增加实用范围和应用方便的优点，具有理论参考价值。

若无特别声明，本文中论及的图均指有限、无向、简单图，没有定义的术语和符号参见文献[3]。为方便叙述，记整数集，其中。对于偶数，偶数集为;对于奇数，奇数集是。记为图G的直径，若、，则记为两点和的距离;设集合 ，如果图的一个标号对任意的，，总有，则为正常标号;此外，让，，若，则称为图G的一个正常有序标号;记集合 正常有序标号}。图G的一个标号，记顶点集 ，边集。若，，如果对任意的，，总有，则为图G的一个强标号（strongly labelling，简记为stl）;记集合为stl} [4-6]，让是一个所有与顶点邻接的顶点集。对于任意的，有，则称为在G图中的层;度为1的顶点称为叶子。

1.1 定义1

给定正数。设图是一条路，有顶点 ;路图有顶，且有拷贝，顶点;， ;顶点分别与顶点 对应，顶点分别与顶点对应，若将对应的每对顶点均用一条边连接;再用一条边连接顶点与顶点，则称所得到的图为图，记集合。

1.2 定义2[7-8]

令为全体整数集合，。设图有标号，。若存在，使得对任意，都有成立，则称为的魔幻广播标号（Magically Radio Labelling，简记），为的魔幻常数，G为图;记集合。

1.3 定义3

设顶点为，的图有，，令，则称为图G的中心。

2 主要结果及证明

2.1 定理

令为全体整数集合，。设图的标号，，;若（1）当时，存在固定的常数与数，使得;（2）当时，存在，使得;则。

2.2 证明

由定义1，设图有标号，边集为 ，;，;顶点集为，;其中 ;让 ，，，;将每对对应点： ，;分别用一条边连接，最后用一条边连接顶点与，所得到的图为图。

以下构造函数并证明，为叙述方便，设，，，。

3 结语

魔幻广播标号和图的定义，图可算法化的方法，它不仅对研究rolg的其它图类有借鉴意义，而且在应用上具有普适性和方便性，这使得它利于深入的研究asrc互不干扰问题，具有理论意义。若，，求定理成立的条件。

参考文献

[1] Devsi Bantva.et.al.Radio number of trees[J].Electronic Notes in Discrete Mathematics，2015（48）：135-141.

[2] Xiangwen Li，Vicky Mak，Sanming Zhou.Optimal radio labellings of complete m-ary trees[J].Discrete applied mathematics，2009（158）：507-505.

[3] Bondy J.A and Murty U.S.R.Graph Theory with Application[M].S.Axler，K.A.Ribet.New York：MaCmillan，1976.

[4] Kathiresan K.M.Two classes of graceful graphs[J].Ars Combinatoria，2000（55）：129-132.

[5] J.MacDougall，M.Miller，Slamin and W.D.Wallis，Vertex-magic total labelings[J].Utilitas. Math，2002（61）：3-21.

[6] Bing Yao，Zhongful Zhang，Ming Yao，Jingwen Li.A New Type of Magical coloring[J].Advances in Mathmatics，2008（37）：571-583.

[7] Ming Yao et al.Bipartite Total Graceful Lablling of Trees[J].Journal of Lanzhou Jiaotong University，2017（36）：132-135.

[8] Joseph A.Gallian.A Dynamic Survey of Graph Labeling[J]. The Electronic Journal of Combinatorics，2007（14）：6-189.