Distinguishing number and distinguishing index of neighbourhood corona of two graphs

Saeid Alikhani; Samaneh Soltani

paper

Distinguishing number and distinguishing index of neighbourhood corona of two graphs

arXiv:1606.03751

Abstract

The distinguishing number (index) $D (G)$ ( $D^{'} (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 neighbourhood corona of two graphs $G_{1}$ and $G_{2}$ is denoted by $G_{1} ⋆ G_{2}$ and is the graph obtained by taking one copy of $G_{1}$ and $∣ V (G_{1}) ∣$ copies of $G_{2}$ , and joining the neighbours of the $i$ th vertex of $G_{1}$ to every vertex in the $i$ th copy of $G_{2}$ . In this paper we describe the automorphisms of the graph $G_{1} ⋆ G_{2}$ . Using results on automorphisms, we study the distinguishing number and the distinguishing index of $G_{1} ⋆ G_{2}$ . We obtain upper bounds for $D (G_{1} ⋆ G_{2})$ and $D^{'} (G_{1} ⋆ G_{2})$ .

15 pages, 11 figures