Stabilizing on the distinguishing number of a graph

Saeid Alikhani, Samaneh Soltani

Published 2016-09-23Version 1

The distinguishing number $D(G)$ of a graph $G$ is the least integer $d$ such that $G$ has a vertex labeling with $d$ labels that is preserved only by a trivial automorphism. The distinguishing stability, of a graph $G$ is denoted by $st_D(G)$ and is the minimum number of vertices whose removal changes the distinguishing number. We obtain a general upper bound $st_D(G) \leqslant \vert V(G)\vert -D(G)+1$, and a relationships between the distinguishing stabilities of graphs $G$ and $G-v$, i.e., $st_D(G)\leqslant st_D(G-v)+1$, where $v\in V(G)$. Also we study the edge distinguishing stability number (distinguishing bondage number) of $G$.