路的字典积的邻和可区别边染色

doi:10.15960/j.cnki.issn.1007-6093.2020.01.011

运筹学学报 ›› 2020, Vol. 24 ›› Issue (1): 140-146.doi: 10.15960/j.cnki.issn.1007-6093.2020.01.011

路的字典积的邻和可区别边染色

田双亮^1,2,*, 杨环¹, 索郎王青¹, 杨青¹

1. 西北民族大学数学与计算机科学学院, 兰州 730030;
2. 西北民族大学动态流数据计算与应用重点实验室, 兰州 730030

收稿日期:2018-03-26 发布日期:2020-03-09
通讯作者: 田双亮 E-mail:sl_tian@163.com
基金资助:
西北民族大学科研创新团队计划资助，国家民委科研资助项目（No.14XBZ018）

Neighbor sum distinguishing edge coloring of the lexicographic product of paths

TIAN Shuangliang^1,2,*, YANG Huan¹, SUOLANG Wangqing¹, YANG Qing¹

1. School of Mathematics and Computer Science, Northwest Minzu University, Lanzhou 730030, China;
2. Key Laboratory of Streaming Data Computing Technologies and Applications, Northwest Minzu University, Lanzhou 730030, China

Received:2018-03-26 Published:2020-03-09

摘要/Abstract

摘要： 图G的正常[k]-边染色σ是指颜色集合为[k]={1，2，…，k}的G的一个正常边染色.用w_σ（x）表示顶点x关联边的颜色之和，即w_σ（x）=∑_e∋x σ（e），并称w_σ（x）关于σ的权.图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色，最小的k值称为G的邻和可区别边色数，记为χ'_∑（G）.现得到了路P_n与简单连通图H的字典积P_n[H]的邻和可区别边色数的精确值，其中H分别为正则第一类图、路、完全图的补图.

关键词: 路, 字典积, 邻和可区别边染色, 邻和可区别边色数

Abstract: A proper[k]-edge coloring σ of graph G is a k-proper-edge-coloring of graph G using colors in[k]={1, 2, …, k}. Let w_σ(x) denote the sum of the colors of edges incident with x, i.e., w_σ(x)=∑_e∋x σ(e), and w_σ(x) is called the weight of the vertex x with respect to σ. A neighbor sum distinguishing edge coloring σ of G is a proper[k]-edge coloring of G such that no pair adjacent vertices receive the same weights. The smallest value k for which G has such a coloring is called the neighbor sum distinguishing edge chromatic number of G and denoted by χ'_∑(G). We obtained the exact values of this parameter for the lexicographic product P_n[H] of a path P_n and a connected simple graph H, where H is a Class 1 regular graph, a path, the complement of a complete graph, respectively.

Key words: path, lexicographic product, neighbor sum distinguishing edge coloring, neighbor sum distinguishing edge chromatic number

中图分类号:

O157.5

田双亮, 杨环, 索郎王青, 杨青. 路的字典积的邻和可区别边染色[J]. 运筹学学报, 2020, 24(1): 140-146.

TIAN Shuangliang, YANG Huan, SUOLANG Wangqing, YANG Qing. Neighbor sum distinguishing edge coloring of the lexicographic product of paths[J]. Operations Research Transactions, 2020, 24(1): 140-146.

参考文献

[1] Zhang Z F, Liu L Z, Wang J F. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15:623-626.
[2] Flandrin E, Marczyk A, Przyby lo J, et al. Neighbor sum distinguishing index[J]. Graphs and Combinatorics, 2013, 29:1329-1336.
[3] Dong A J,Wang G H, Zhang J H. Neighbor sum distinguishing edge colorings of graphs with bounded maximum average degree[J]. Discrete Applied Mathematics, 2014, 166:84-90.
[4] Hu X L, Chen Y J, Luo R, et al. Neighbor sum distinguishing edge colorings of sparse graphs[J]. Discrete Applied Mathematics, 2015, 193:119-125.
[5] Yu X W, Gao Y P, Ding L H. Neighbor sum distinguishing chromatic index of sparse graphs via the combinatorial Nullstellensatz[J]. Acta Mathematicae Applicatae Sinica, English Series, 2018, 34(1):135-144.
[6] Yu X W, Wang G H, Wu J L. Neighbor sum distinguishing edge coloring of subcubic graphs[J]. Acta Mathematica Sinica, English Series, 2017, 33(2):252-262.
[7] Gao Y P, Wang G H, Wu J L. Neighbor sum distinguishing edge colorings of graphs with small maximum average degree[J]. Bulletin Malaysian Mathematical Science Society, 2016, 39:S247-S256.
[8] Hocquard H, Przyby lo J. On the neighbour sum distinguishing index of graphs with bounded maximum average degree[J]. Graphs and Combinatorics, 2017, 33:1459-1471.
[9] Qiu B J, Wang J H, Liu Y. Neighbor sum distinguishing colorings of graphs with maximum average degree less than 3712[J]. Acta Mathematica Sinica, English Series, 2018, 34(2):265-274.
[10] Hu X L, Chen Y J, Luo R, et al. Neighbor sum distinguishing index of 2-degenerate graphs[J]. Journal of Combinatorial Optimization, 2017, 34:798-809.
[11] Zhang J H, Ding L H, Wang G H, et al. Neighbor sum distinguishing index of K₄-minor free graphs[J]. Graphs and Combinatorics, 2016, 32:1621-1633.
[12] Bondy J A, Murty U S R. Graph Theory with Applications[M]. New York:Elsevier, 1976.

[1]	黄志鹏, 李兴权, 朱文兴. 超大规模集成电路布局的优化模型与算法[J]. 运筹学学报, 2021, 25(3): 15-36.
[2]	孙广磊, 李小申, 尚有林. 基于时变需求的集成多级供应链生产订货策略研究[J]. 运筹学学报, 2019, 23(4): 143-154.
[3]	刘岩, 雷梦霞, 黄晓娴. 最大匹配的路变换图[J]. 运筹学学报, 2019, 23(2): 104-112.
[4]	刁卓. 不确定性自私路由模型的理论和应用[J]. 运筹学学报, 2019, 23(1): 119-126.
[5]	苏振华. 六阶图C_6+3K_2与P_n, C_n的联图交叉数[J]. 运筹学学报, 2017, 21(3): 23-34.
[6]	何志权. 资产跳跃下CM策略多期收入保证价格模拟[J]. 运筹学学报, 2017, 21(1): 87-102.
[7]	周志东, 李龙 . 一个特殊6点图Q与nK_{1}, P_{n}及C_{n}的联图交叉数[J]. 运筹学学报, 2016, 20(4): 115-126.
[8]	韩世莲. 求解物流运输网络SUM-MIN双目标路径问题的扩展标号法[J]. 运筹学学报, 2016, 20(3): 121-128.
[9]	刘长河, 尚有林, 李锦睿. 基于一类新方向的宽邻域路径跟踪内点算法[J]. 运筹学学报, 2016, 20(1): 43-53.
[10]	管梅谷. 关于中国邮递员问题研究和发展的历史回顾[J]. 运筹学学报, 2015, 19(3): 1-7.
[11]	宁涛, 陈荣, 郭晨, 梁旭. 一种基于双链量子编码的动态车辆路径问题解决策略[J]. 运筹学学报, 2015, 19(2): 72-82.
[12]	何胜学. 无预警紧急疏散中公交车辆路径的确定方法[J]. 运筹学学报, 2014, 18(3): 47-59.
[13]	丁录顺, 王光辉, 颜谨. 不含三角形图的正常染色路和正常染色圈[J]. 运筹学学报, 2014, 18(3): 116-120.
[14]	余桂东, 张超, 龚奇娟. 图的能量与哈密尔顿性[J]. 运筹学学报, 2014, 18(2): 40-48.
[15]	单而芳, 叶婷婷. 几类积图的团染色数[J]. 运筹学学报, 2013, 17(4): 103-108.

路的字典积的邻和可区别边染色

Neighbor sum distinguishing edge coloring of the lexicographic product of paths

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价