若干图的广义字典积的点可区别边染色

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

在图G与不相交图序列hn=(Hi)i∈{0,1,…,n-1}的广义字典积G[hn]中,若Hi≌H,i=0,1,…,n-1,则将G[hn]记为G[H],其中G[H]是G与H的字典积。图G的点可区别边染色所需最少的颜色数称为G的点可区别边色数,记为χ'vd(G)。对任一满足χ'vd(G)=Δ(G)的图G,给出了参数χ'vd(G[hn])的两个上界,并证明这些上界是可达到的,其中hn=(Hi)i∈{0,1,…,n-1}中的每一个Hi均为m阶简单图。另外证明了:如果χ'vd(G)=Δ(G),χ'vd(H)=Δ(H)且Δ(G[H])=Δ(H[G]),则χ'vd(G[H])=χ'vd(H[G]),其中G与H分别为n阶与m阶的简单图。

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 prov＋ed 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.