THE DISTINGUISHING NUMBER AND DISTINGUISHING INDEX OF THE LEXICOGRAPHIC PRODUCT OF TWO GRAPHS

The distinguishing number (index) D(G) (D'(G)) of a graph G is the least integer d such that G has a vertex labeling (edge labeling) with d labels that is preserved only by the trivial automorphism. The lexicographic product of two graphs G and H, G[H] can be obtained from G by substituting a copy H-u of H for every vertex u of G and then joining all vertices of H-u with all vertices of H if uv epsilon E(G). In this paper we obtain some sharp bounds for the distinguishing number and the distinguishing index of the lexicographic product of two graphs. As consequences, we prove that if G is a connected graph with Aut(G[G]) = Aut(G)[Aut(G)], then for every natural number k, D(G) <= D(G(k)) <= D(G) + k - 1 and all lexicographic powers of G, G(k) (k >= 2) can be distinguished by two edge labels, where G(k) = G[G[ . . . ]].