中文

Operations Research Transactions >

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

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

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

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

Cite this article

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 . DOI: 10.15960/j.cnki.issn.1007-6093.2020.01.011

References

[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
Outlines

/

〈 〉