On the relationship between distinguishing number and distinguishing index of a graph

Saeid Alikhani, Samaneh Soltani

Published 2016-08-11Version 1

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. Motivated by a theorem (Kalinowski and Pil\'sniak, 2015) which state that for every graph of order $n \geqslant 3$, $D'(G) \leqslant D(G) + 1$, we characterize all finite simple connected graphs with $D'(G) = D(G) + 1$. Also, we describe all finite simple connected graphs with $D'(G) = D(G)$ and $| E(G)| \leqslant | V(G)|$.