JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)

Previous Articles     Next Articles

Vertex-distinguishing edge coloring of the generalized lexicographic product of some graphs#br#

TIAN  Shuang-liang   

  1. School of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, Gansu, China
  • Received:2013-12-30 Online:2014-06-20 Published:2014-06-14

Abstract: For the generalized lexicographic product G[hn] of a graph G and a sequence of vertex disjoint graphs hn=(Hi)i∈{0,1,…,n-1}, if HiH for i=0,1,…,n-1, then G[hn]=G[H], where G[H] is the lexicographic product of two graphs. The minimum number of colors required for a vertexdistinguishing edge coloring of G is called the vertexdistinguishing edge chromatic number of G and denoted by  χ′vd(G). For any graph G with  χ′vd (G)=Δ(G), two upper bounds on the parameter χ′vd (G[hn]) are provided in this paper and those are proved to be attainable precisely, where every Hi is a simply graph of order m. It is also proved that if χ′vd(G)=Δ(G), χ′vd(H)=Δ(H) and Δ(G[H])=Δ(H[G]), then χ′vd (G[H])=χ′vd (H[G]), where G and H are simply graphs of order n and m, respectively.

Key words: vertex-distinguishing edge chromatic number, lexicographic product, generalized lexicographic product, vertexdistinguishing edge coloring

[1] WANG Dong-yan, LI Shenggang*, YANG Wen-hua. The product operations and related decompostions of fuzzy graphs [J]. J4, 2013, 48(6): 104-110.
[2] TIAN Shuang-liang. Vertex-distinguishing edge colorings of the Mycielski′s graphs of  some lexicographic product graphs [J]. J4, 2012, 47(8): 7-10.
[3] LI Lin,WANG Zhi-wen,LI Jing-wen,WEN Fei. The vertex distinguishing edge coloring chromatic number of Kn-{vn-5 vn-4,vn-3 vn-2,vn-1 vn}(n≥14,n≡0(mod2)) [J]. J4, 2010, 45(4): 27-30.
[4]

LI Jing-wen ,XU Bao-gen,LI Mu-chun ,ZHANG Zhong-fu ,ZHAO Chuan-cheng ,REN Zhi-guo

. On the vertex-distinguishing chromatic number of Pm∨Cn [J]. J4, 2008, 43(8): 24-27 .
[5] SHUANG Liang,CHEN Ping . On the vertexdistinguishing edge colorings of some product graphs [J]. J4, 2006, 41(4): 53-56 .
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!