Distinguishing number and distinguishing index of strong 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 strong product $G⊠H$ of two graphs $G$ and $H$ is the graph with vertex set $V(G)\times V(H)$ and edge set $\{\{(x_1,x_2),(y_1,y_2)\}|x_i{y}_i\in E(G_i)\mathrm{or}{x}_i=y_i\mathrm{for}\mathrm{each}1\le i\le 2.\}$. In this paper we study the distinguishing number and the distinguishing index of strong product of two graphs. We prove that for every $k\ge 2$, the $k$-th strong power of a connected $S$-thin graph $G$ has distinguishing index equal 2.

6 pages