若干联图的
L （2，1）-边染色算法L （2，1）-edge coloring algorithm for some composite graphs- 中山大学学报(自然科学版)(中英文) 2023年62卷第3期 页码：175-183
- 作者机构：
兰州交通大学电子与信息工程学院，甘肃 兰州 730070
- 作者简介：
朱利娜（1996年生），女；研究方向：图论算法及其应用；E-mail：zhul366930@126.com
李敬文（1965年生），男；研究方向：图论算法及其应用；E-mail：lijingwen28@163.com
- 基金信息：国家自然科学基金(11961041;62062049;11461038);甘肃省科技计划(21ZD8RA008)
DOI：10.13471/j.cnki.acta.snus.2021A032
中图分类号： O157.5纸质出版日期：2023-05-25，
网络出版日期：2023-03-26，
收稿日期：2021-04-23，
录用日期：2022-02-19
扫 描 看 全 文
朱利娜,李敬文,孙帅.若干联图的L（2，1）-边染色算法[J].中山大学学报(自然科学版),2023,62(03):175-183.
ZHU Lina,LI Jingwen,SUN Shuai.L（2，1）-edge coloring algorithm for some composite graphs[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2023,62(03):175-183.
朱利娜,李敬文,孙帅.若干联图的L（2，1）-边染色算法[J].中山大学学报(自然科学版),2023,62(03):175-183. DOI： 10.13471/j.cnki.acta.snus.2021A032.
ZHU Lina,LI Jingwen,SUN Shuai.L（2，1）-edge coloring algorithm for some composite graphs[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2023,62(03):175-183. DOI： 10.13471/j.cnki.acta.snus.2021A032.
摘要
图的距离染色问题是频率分配问题的一种图模型，所谓的频率分配问题是指某一区域的不同电台要使用无线电波发送信号，为了避免干扰，位置较近的电台需要使用不同的频道，当电台距离特别近时，它们之间需要间隔至少2个信道。
<math id="M1"><mi>L</mi><mfenced separators="|"><mrow><mn mathvariant="normal">2
1</mn></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49418964&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49418944&type=
9.22866726
3.38666677
-边染色是指距离为1的两条边的色数差值大于等于2，距离大于1的两条边的色数不同。本文针对随机图设计了一种
<math id="M2"><mi>L</mi><mfenced separators="|"><mrow><mn mathvariant="normal">2
1</mn></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49419006&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49418997&type=
9.22866726
3.38666677
-边染色算法，实验结果表明，该算法能够解决有限点内随机图的
<math id="M3"><mi>L</mi><mfenced separators="|"><mrow><mn mathvariant="normal">2
1</mn></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49419006&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49418997&type=
9.22866726
3.38666677
-边染色问题。通过分析实验结果，发现了3类单圈图的染色特性，定义
<math id="M4"><msub><mrow><mi>C</mi></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msub><mo>↑</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>↑</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49419041&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49419047&type=
19.55800056
4.14866638
，
<math id="M5"><msub><mrow><mi>C</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>↓</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49419088&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49419079&type=
11.26066685
4.14866638
和
<math id="M6"><msub><mrow><mi>C</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>↑</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49419117&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49419098&type=
11.26066685
4.14866638
分别来刻画这三类单圈图，并给出相关定理及其证明。
Abstract
The distance coloring problem of graph is a graph model for frequency allocation problem. The so-called frequency allocation problem refers to that different radio stations in a certain area need to use radio waves to send signals. In order to avoid interference， stations in close proximity need to use different channels， and when stations are particularly close， they need to be separated by at least two channels.
<math id="M7"><mi>L</mi><mfenced separators="|"><mrow><mn mathvariant="normal">2
1</mn></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422749&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422736&type=
10.75266743
3.89466691
-edge coloring means that the chromatic number difference of two edges with distance 1 is greater than or equal to 2， and the chromatic number of two edges with distance greater than 1 is different. In this paper， an
<math id="M8"><mi>L</mi><mfenced separators="|"><mrow><mn mathvariant="normal">2
1</mn></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422749&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422736&type=
10.75266743
3.89466691
-edge coloring algorithm is designed for random graphs. According to the experimental results， it is shown that the
<math id="M9"><mi>L</mi><mfenced separators="|"><mrow><mn mathvariant="normal">2
1</mn></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422749&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422736&type=
10.75266743
3.89466691
-edge coloring problem of random graphs in finite points can be solved through the algorithm. Meanwhile， the coloring properties of three kinds of unicyclic graphs are found here， and we define
<math id="M10"><msub><mrow><mi>C</mi></mrow><mrow><mn mathvariant="normal">3</mn></mrow></msub><mo>↑</mo><msub><mrow><mi>P</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>↑</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422740&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422750&type=
22.69066620
4.82600021
，
<math id="M11"><msub><mrow><mi>C</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>↓</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422754&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422742&type=
13.12333298
4.82600021
and
<math id="M12"><msub><mrow><mi>C</mi></mrow><mrow><mi>n</mi></mrow></msub><mo>↑</mo><msub><mrow><mi>S</mi></mrow><mrow><mi>m</mi></mrow></msub></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422756&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422745&type=
13.12333298
4.82600021
to characterize these three kinds of unicyclic graphs respectively. The related theorems and proofs are given as well.
关键词
<math id="M13"><mi>L</mi><mfenced separators="|"><mrow><mn mathvariant="normal">21</mn></mrow></mfenced></math>https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49419297&type=https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49419280&type=9.228667263.38666677-边染色色数单圈图算法
Keywords
<math id="M14"><mi>L</mi><mfenced separators="|"><mrow><mn mathvariant="normal">21</mn></mrow></mfenced></math>https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422749&type=https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=49422736&type=10.752667433.89466691-edge coloringchromatic numberunicyclic graphalgorithm
references
陈琴， 2006. 图的L（2，1）-边标号［D］.南京：东南大学.
孙帅，李敬文，袁清厚，2021. 随机图的L（2，1）-标号混合人工蜂群算法［J］.武汉大学学报（理学版），67（2）：158-164.
ASLAN S，2020. A comparative study between artificial bee colony （ABC） algorithm and its variants on big data optimization［J］. Memetic Comp，12（2）：129-150.
GRIGGS J R， YEH R K， 1992. Labelling graphs with a condition at distance 2［J］. SIAM J Discrete Math， 5（4）： 586-595.
HALE W K, 1980. Frequency assignment: Theory and applications[J]. Proc IEEE, 68(12): 1497-1514.
ROBERTS F S，1991. T-colorings of graphs: recent results and open problems[J]. Discrete Math, 93(2/3): 229-245.
0
浏览量
1
下载量
0
CSCD
- 网络PDF下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
- 地址：广州市海珠区新港西路135号 中山大学南校园东北区311栋 邮编：510275
- 联系电话：020-84112585，84113223 Email：xuebaozr@mail.sysu.edu.cn
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies
