2-Distance sum distinguishing edge colorings of square graphs

• 1:上海工程技术大学数理与统计学院

• 2:智能计算与应用统计研究中心

• 3:西北师范大学数学与统计学院

• 
  

摘要(Abstract)：

为了进一步研究图的2-距离和可区别边染色的问题.利用组合分析法、反证法以及分类讨论的思想，得到了路、圈、C_n∧P_m、C_m∧C_n、C_n∧P_m∧C_k等5类平方图的2-距离和可区别边色数，结果表明这5类平方图的2-距离和可区别边色数均不超过Δ+2.
This paper is to further study the problem of the 2-distance sum distinguishing edge coloring of graphs. By using the methods of combinatorial analysis, reduction to absurdity and categorical discussion, the 2-distance sum distinguishing edge chromatic numbers of five types of square graphs including paths, cycles, C_n∧P_m, C_m∧C_n and C_n∧P_m∧C_k are determined, respectively. The above results implies that the 2-distance sum distinguishing edge chromatic numbers are no more than Δ+2.

关键词(KeyWords)：边染色;2-距离和可区别边染色;平方图
edge coloring;2-distance sum distinguishing edge coloring;square graphs

基金项目(Foundation):国家自然科学基金(61672001;61662066;62072296)

作者(Authors):王芹;杨超;姚兵;
Wang Qin;Yang Chao;Yao Bing;School of Mathematics, Physics and Statistics, Center of Intelligent Computing and Applied Statistics, Shanghai University of Engineering Science;College of Mathematics and Statistics, Northwest Normal University;

DOI:10.16366/j.cnki.1000-2367.2023.04.010

参考文献(References)：

• [1] ZHANG Z F,LIU L Z,WANG J F.Adjacent strong edge coloring of graphs[J].Applied Mathematics Letters,2002,15(5):623-626.

• [2] 安卓莫，田双亮，蔡瑾.路的强积的邻点可区别边染色[J].西北民族大学学报(自然科学版),2020,41(4):7-10.AN Z M,TIAN S L,CAI J.Adjacent vertex distinguishing edge coloring of strong product of paths[J].Journal of Northwest Minzu University(Natural Science),2020,41(4):7-10.

• [3] BURRIS A C,SCHELP R H.Vertex-distinguishing proper edge-colorings[J].Journal of Graph Theory,1997,26(2):73-82.

• [4] 张小秀.平面图的邻点可区别边染色[D].金华：浙江师范大学，2020.ZHANG X X.Adjacent vertex distinguishing edge coloring of planar graphs[D].Jinhua:Zhejiang Normal University,2020.

• [5] 张小秀，黄丹君.围长至少为5的平面图的邻点可区别边染色[J].数学学报(中文版),2022,65(2):325-334.ZHANG X X,HUANG D J.Adjacent vertex distinguishing edge coloring of planar graphs with girth at least 5[J].Acta Mathematica Sinica(Chinese Series),2022,65(2):325-334.

• [6] WANG W F,WANG Y Q.Adjacent vertex-distinguishing edge colorings of K4-minor free graphs[J].Applied Mathematics Letters,2011,24(12):2034-2037.

• [7] 严谦泰，张忠辅.一类正则二部图的邻强边染色[J].betway官方app 学报(自然科学版),2006,34(3):12-13.YAN Q T,ZHANG Z F.On the adgacent strong edge coloring of r-regular partite graph[J].Journal of Henan Normal University(Natural Science Edition),2006,34(3):12-13.

• [8] 王治文，文飞，杨随义，等.图K2n|E(F5)(n≥13)的点可区别边染色[J].betway官方app 学报(自然科学版),2010,38(6):1-3.WANG Z W,WEN F,YANG S Y,et al.Vertex-distinguishing edge coloring of K2n|E(F5)(n≥13)[J].Journal of Henan Normal University(Natural Science Edition),2010,38(6):1-3.

• [9] FLANDRIN E,MARCZYK A,PRZYBYLO J,et al.Neighbor sum distinguishing index[J].Graphs and Combinatorics,2013,29(5):1329-1336.

• [10] 强会英，姚丽.无K4-子式图的2-距离和可区别边染色[J].山东大学学报(理学版),2021,56(11):83-86.QIANG H Y,YAO L.2-distance sum distinguishing edge coloring of K4-minor-free graphs[J].Journal of Shandong University(Natural Science),2021,56(11):83-86.

• [11] WEGNER G.Graphs with given diameter and coloring problem[R].Dortmund:University of Dortmund,1977.

• [12] 姚丽.几类图的2-距离和可区别染色[D].兰州：兰州交通大学，2021.YAO L.2-distance sum distinguishing coloring of several kinds of graphs[D].Lanzhou:Lanzhou Jiaotong University,2021.

• [13] BONDY J A,MURTY U S R.Graph theory with applications[M].London:The MaCmillan Press,1976.

平方图的2-距离和可区别边染色.pdf