Adjacent vertex distinguishing edge-colorings and total-colorings of the lexicographic product of graphs

作者：Tian, Shuangliang^*; Wang, Qian

来源：Discrete Applied Mathematics, 2015, 185: 220-226.

DOI：10.1016/j.dam.2014.11.028

• Edge-coloring
• Total-coloring
• Adjacent vertex distinguishing edge-coloring
• Adjacent vertex distinguishing total-coloring
• Lexicographic product

Let G be a simple graph with vertex set V (G) and edge set E(G). An edge-coloring f of G is called an adjacent vertex distinguishing edge-coloring of G if C-f (u) not equal C-f (v) for any uv is an element of E(G), where C-f (u) denotes the set of colors of edges incident with u. A total-coloring g of G is called an adjacent vertex distinguishing total-coloring of G if S-g (u) not equal S-g(v) for any uv is an element of E(G), where S-g(u) denotes the set of colors of edges incident with u together with the color assigned to u. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring (resp. an adjacent vertex distinguishing total-coloring) of G is denoted by chi(a)'(G) (resp. chi(at) (G)). The lexicographic product of simple graphs G and H is simple graph G[H] with vertex set V (G) x V (H), in which (u, v) is adjacent to (u', v') if and only if either uu' is an element of E(G) or u = u' and vv' is an element of E(H). In this paper, we consider these parameters for the lexicographic product G[H] of two graphs G and H. We give the exact values of chi(a)'(G[H]) if (1) G is a complete graph of order n >= 3 and H is a graph of order 2m >= 4 with chi(a)'(H) = Delta(H); (2) G is a tree of order is >= 3 and H is a graph of order m >= 3 with chi(a)'(H) = Delta(H).
We also obtain the exact values of chi(at) (G[H]) if (1) G is a complete graph of order n >= 2 and His an empty graph of order m >= 2, where nm is even; (2) G is a complete graph of order n >= 2 and H is a bipartite graph of order m >= 4 with bipartition (X, Y), where vertical bar X vertical bar and vertical bar Y vertical bar are even; (3) G is a cycle of order is >= 3 and H is an empty graph of order in >= 2,1 where nm is even; (4) G is a tree of order n > 3 and H is an empty graph of order in >= 2.

• 出版日期2015-4-20
• 单位西北民族大学