کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419314 | 683778 | 2015 | 7 صفحه PDF | دانلود رایگان |
Let GG be a simple graph with vertex set V(G)V(G) and edge set E(G)E(G). An edge-coloring ff of GG is called an adjacent vertex distinguishing edge-coloring of GG if Cf(u)≠Cf(v)Cf(u)≠Cf(v) for any uv∈E(G)uv∈E(G), where Cf(u)Cf(u) denotes the set of colors of edges incident with uu. A total-coloring gg of GG is called an adjacent vertex distinguishing total-coloring of GG if Sg(u)≠Sg(v)Sg(u)≠Sg(v) for any uv∈E(G)uv∈E(G), where Sg(u)Sg(u) denotes the set of colors of edges incident with uu together with the color assigned to uu. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring (resp. an adjacent vertex distinguishing total-coloring) of GG is denoted by χa′(G) (resp. χat(G)χat(G)). The lexicographic product of simple graphs GG and HH is simple graph G[H]G[H] with vertex set V(G)×V(H)V(G)×V(H), in which (u,v)(u,v) is adjacent to (u′,v′)(u′,v′) if and only if either uu′∈E(G)uu′∈E(G) or u=u′u=u′ and vv′∈E(H)vv′∈E(H). In this paper, we consider these parameters for the lexicographic product G[H]G[H] of two graphs GG and HH. We give the exact values of χa′(G[H]) if (1) GG is a complete graph of order n≥3n≥3 and HH is a graph of order 2m≥42m≥4 with χa′(H)=Δ(H); (2) GG is a tree of order n≥3n≥3 and HH is a graph of order m≥3m≥3 with χa′(H)=Δ(H).We also obtain the exact values of χat(G[H])χat(G[H]) if (1) GG is a complete graph of order n≥2n≥2 and HH is an empty graph of order m≥2m≥2, where nmnm is even; (2) GG is a complete graph of order n≥2n≥2 and HH is a bipartite graph of order m≥4m≥4 with bipartition (X,Y)(X,Y), where |X||X| and |Y||Y| are even; (3) GG is a cycle of order n≥3n≥3 and HH is an empty graph of order m≥2m≥2, where nmnm is even; (4) GG is a tree of order n≥3n≥3 and HH is an empty graph of order m≥2m≥2.
Journal: Discrete Applied Mathematics - Volume 185, 20 April 2015, Pages 220–226