The distinguishing number and the distinguishing index of co-normal 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 co-normal product $G\star 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_1{y}_1\in E(G)\mathrm{or}{x}_2{y}_2\in E(H)\}$. In this paper we study the distinguishing number and the distinguishing index of the co-normal product of two graphs. We prove that for every $k\ge 3$, the $k$-th co-normal power of a connected graph $G$ with no false twin vertex and no dominating vertex, has the distinguishing number and the distinguishing index equal two.

arXiv comment8 pages. arXiv admin note: text overlap with arXiv:1703.01874

References in corpus (1)

• On automorphisms and fixing number of co-normal product of graphs