JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2023, Vol. 58 ›› Issue (8): 63-72.doi: 10.6040/j.issn.1671-9352.0.2021.513

Previous Articles     Next Articles

L(2, 1)- edge coloring algorithm for several kinds of composite graphs

Lina ZHU(),Jingwen LI*(),Shuai SUN   

  1. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China
  • Received:2021-08-17 Online:2023-08-20 Published:2023-07-28
  • Contact: Jingwen LI E-mail:3072039233@qq.com;lijingwen28@163.com

RichHTML

2

PDF (PC)

62

Abstract:

An L(2, 1)- edge coloring algorithm is designed to solve the L(2, 1)- edge coloring for random graphs. By analyzing the experimental results, the coloring properties of five classes of join graphs are found, and Fn↑Sm、Cn↑Cm、Fn(2)、C3(n)↑Sm and Cn(m) are used to describe these graphs. The related theorems and proofs are given as well.

Key words: L(2, 1)- edge coloring, chromatic number, composite graphs, algorithm

CLC Number: 

  • O157.5

Fig.1

Example of G↑H"

Fig.2

Example of Cn(m)"

Table 1

L(2, 1)-edge coloring number of graphs within 11 points"

染色跨度 点数
3 4 5 6 7 8 9 10
Δ+1 0 2 3 2 2 2 5 4
Δ+2 1 2 7 17 32 63 122 290
Δ+3 0 1 7 30 98 289 872 2 740
Δ+4 0 1 2 28 146 649 2 916 12 664
Δ+5 0 0 2 15 136 1 037 6 431 39 338
Δ+6 0 0 0 9 140 1 350 12 252 99 986
Δ+7 0 0 0 6 111 1 553 18 727 207 699
Δ+8 0 0 0 3 90 1 659 25 206 368 272
Δ+9 0 0 0 1 51 1 456 29 834 578 938
Δ+10 0 0 0 1 30 1 106 32 771 824 978
Δ+11 0 0 0 0 7 797 31 555 1 059 707
Δ+12 0 0 0 0 6 506 28 313 1 218 095
Δ+13 0 0 0 0 2 327 22 872 1 278 529
Δ+14 0 0 0 0 0 156 17 606 1 244 017
Δ+15 0 0 0 0 1 83 12 084 1 146 528
Δ+16 0 0 0 0 12 48 8 128 997 517
Δ+17 0 0 0 0 0 18 5 090 830 287
Δ+18 0 0 0 0 0 9 3 037 687 759
Δ+19 0 0 0 0 0 5 1 709 570 315
Δ+20 0 0 0 0 0 2 915 426 317
Δ+21 0 0 0 0 0 1 375 259 821
Δ+22 0 0 0 0 0 15 154 149 071
Δ+23 0 0 0 0 0 0 65 95 342
Δ+24 0 0 0 0 0 0 24 55 577
Δ+25 0 0 0 0 0 0 8 28 543
Δ+26 0 0 0 0 0 0 5 15 130
Δ+27 0 0 0 0 0 0 2 5 514
Δ+28 0 0 0 0 0 0 1 1 416
Δ+29 0 0 0 0 0 0 1 515
Δ+30 0 0 0 0 0 0 0 179
Δ+31 0 0 0 0 0 0 0 75
Δ+32 0 0 0 0 0 0 0 27
Δ+33 0 0 0 0 0 0 0 9
Δ+34 0 0 0 0 0 0 0 5
Δ+35 0 0 0 0 0 0 0 2
Δ+36 0 0 0 0 0 0 0 1
Δ+37 0 0 0 0 0 0 0 1
图总数 1 6 21 112 853 11 117 261 080 12 205 208

Fig.3

Examples of edge coloring of Fn↑Sm"

Fig.4

Examples of edge coloring of Cn↑Cm"

Fig.5

Examples of edge coloring of Fn(2)"

Fig.6

Examples of edge coloring of C3(4)↑S5"

Fig.7

Examples of edge coloring of Cn(m)(3≤n≤6)"

1 HALE W K . Frequency assignment: theory and applications[J]. Proceedings of the IEEE, 1980, 68, 1497- 1514.
doi: 10.1109/PROC.1980.11899
2 GRIGGS J R , YEH R K . Labelling graphs with a condition at distance 2[J]. SIAM Journal on Discrete Mathematics, 1992, 5 (4): 586- 595.
doi: 10.1137/0405048
3 陈琴. 图的L(2, 1)-边标号[D]. 南京: 东南大学, 2006.
CHEN Qin. L(2, 1)-Edge-labeling of graphs[D]. Nanjing: Southeast University, 2006.
4 ASLAN S . A comparative study between artificial bee colony (ABC) algorithm and its variants on big data optimization[J]. Memetic Computing, 2020, 12 (2): 129- 150.
doi: 10.1007/s12293-020-00298-2
5 CHEN Q , LIN W S . L(j, k)-labelings and L(j, k)-edge-labelings of graphs[J]. ARS Combinatoria -Waterloo Then Winnipeg-, 2012, 106, 161- 172.
6 孙帅, 李敬文, 袁清厚. 随机图的L(2, 1)-标号混合人工蜂群算法[J]. 武汉大学学报(理学版), 2021, 67 (2): 158- 164.
SUN Shuai , LI Jingwen , YUAN Qinghou . A hybrid artificial bee colony algorithm for L(2, 1)-labelling of random graph[J]. Journal of Wuhan University (Natural Science Edition), 2021, 67 (2): 158- 164.
[1] LU Jianwei, REN Jizhou, GUAN Jie. Research on cryptographic properties of generalized SIMON-like round functions [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(9): 51-58.
[2] XU Huachang, XU Qian, ZHAO Yulin, LIANG Fengning, XU Kai, ZHU Hong. Prediction method of IDH1 mutation status of glioma based on improved EfficientNetV2 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(7): 60-66.
[3] LIU Haiyan, TUO Shouheng. A new filled function method for global optimization [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(7): 80-87.
[4] ZHANG Jinke, ZHANG Jiangang. Signal detection and fault diagnosis based on improved particle swarm optimization algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(5): 63-75.
[5] REN Shi-xian, AN Jing. An efficient spectral approximation for the transmission eigenvalue problem in spherical domains [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(4): 8-15.
[6] ZHONG Chengcheng, ZHOU Heng, ZHANG Zitong, ZHANG Chunlei. LAC-UNet: semantic segmentation model based on capsules for representing part-whole hierarchical features [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 116-126.
[7] LAN Linyu, LI Jingwen, ZHANG Shucheng, ZHANG Lijing, SHEN Huayu. Vertex reducibletotal labeling algorithm for graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 135-146.
[8] LIANG Yun, MEN Chang-qian, WANG Wen-jian. AdaBoost algorithm based on model decision tree [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(1): 67-75.
[9] CHEN Shu-zhen, LI Shou-wei, SHI Kai-quan. Network security acquisition of evidence reasoning and retrieval data [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(1): 1-9.
[10] LI Shou-wei, SHI Kai-quan. Inverse separated fuzzy set ((-overA)F,(-overA)(-overF)) and secure acquisition of fuzzy information [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(9): 1-14.
[11] GUO Jing-jun, WANG Yu-bing, BAI Ya-nan. American option pricing and simulation under the mixed fractional Heston-CIR model [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(9): 46-54.
[12] LIU Yun, SONG Kai, CHEN Lu-yao, ZHU Peng-jun. Trust management optimization of wireless sensor network nodes based on blockchain using equilibrium evaluation algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(7): 73-84.
[13] ZHAO Ya-di, CHEN Xiang-en. Vertex-distinguishing Ⅰ-total colorings of mC14 [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(6): 54-60.
[14] YANG Teng-fei, XU Chang-qing. Total colorings of 3-degenerate graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(6): 61-63.
[15] WU Wan-qing, ZHOU Guo-long, WANG Qiao, ZHAO Yong-xin. Research of balanced Boolean functions with high nonlinearity based on GSA [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(5): 74-84.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LUO Si-te, LU Li-qian, CUI Ruo-fei, ZHOU Wei-wei, LI Zeng-yong*. Monte-Carlo simulation of photons transmission at alcohol wavelength in  skin tissue and design of fiber optic probe[J]. J4, 2013, 48(1): 46 -50 .
[2] TIAN Xue-gang, WANG Shao-ying. Solutions to the operator equation AXB=C[J]. J4, 2010, 45(6): 74 -80 .
[3] HUO Yu-hong, JI Quan-bao. Synchronization analysis of oscillatory activities in a biological cell system[J]. J4, 2010, 45(6): 105 -110 .
[4] TANG Feng-qin1, BAI Jian-ming2. The precise large deviations for a risk model with extended negatively upper orthant dependent claim  sizes[J]. J4, 2013, 48(1): 100 -106 .
[5] CHENG Zhi1,2, SUN Cui-fang2, WANG Ning1, DU Xian-neng1. On the fibre product of Zn and its property[J]. J4, 2013, 48(2): 15 -19 .
[6] TANG Xiao-hong1, HU Wen-xiao2*, WEI Yan-feng2, JIANG Xi-long2, ZHANG Jing-ying2, SHAO Xue-dong3. Screening and biological characteristics studies of wide wine-making yeasts[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 12 -17 .
[7] ZHAO Jun1, ZHAO Jing2, FAN Ting-jun1*, YUAN Wen-peng1,3, ZHANG Zheng1, CONG Ri-shan1. Purification and anti-tumor activity examination of water-soluble asterosaponin from Asterias rollestoni Bell[J]. J4, 2013, 48(1): 30 -35 .
[8] YANG Yong-wei1, 2, HE Peng-fei2, LI Yi-jun2,3. On strict filters of BL-algebras#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 63 -67 .
[9] LI Min1,2, LI Qi-qiang1. Observer-based sliding mode control of uncertain singular time-delay systems#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(03): 37 -42 .
[10] HE Hai-lun， CHEN Xiu-lan* . Circular dichroism detection of the effects of denaturants and buffers on the conformation of cold-adapted protease MCP-01 and  mesophilic protease BP01[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2013, 48(1): 23 -29 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd