Distinguishing number and distinguishing index of lexicographic product of two graphs

Abstract

The distinguishing number (index) $D(G)$ ($D^{\prime }(G)$) of a graph $G$ is the least integer $d$ such that $G$ has an vertex labeling (edge labeling) with $d$ labels that is preserved only by a 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_v$ if $uv\in E(G)$. In this paper we obtain some sharp bounds for the distinguishing number and the distinguishing index of lexicographic product of two graphs. As consequences, we prove that if $G$ is a connected graph with a special condition on automorphism group of $G[G]$ and $D(G)>1$, then for every natural $k$, $D(G)\le D(G^k)\le D(G)+k-1$, where $G^k=G[G[...]]$. Also we prove that all lexicographic powers of $G$, $G^k$ ($k\ge 2$) can be distinguished by at most two edge labels.

11 pages, 2 figures. arXiv admin note: text overlap with arXiv:1606.03751