Distinguishing number and distinguishing index of Kronecker 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 Kronecker product $G\times H$ of two graphs $G$ and $H$ is the graph with vertex set $V(G)\times V(H)$ and edge set $\{\{(u,x),(v,y)\}|\{u,v\}\in E(G)and\{x,y\}\in E(H)\}$. In this paper we study the distinguishing number and the distinguishing index of Kronecker product of two graphs.

10 pages, 3 figures