English

运筹学学报 >

2020 , Vol. 24 >Issue 1: 140 - 146

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2020.01.011

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

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

收稿日期: 2018-03-26

  网络出版日期: 2020-03-09

基金资助

西北民族大学科研创新团队计划资助，国家民委科研资助项目（No.14XBZ018）

收起

Neighbor sum distinguishing edge coloring of the lexicographic product of paths

Expand
  • 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 date: 2018-03-26

  Online published: 2020-03-09

Fold

摘要

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

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

本文引用格式

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

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 Pn[H] of a path Pn 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

参考文献

[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 K4-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.
Options
文章导航

/

〈 〉