Stabilizing on the distinguishing number of a graph

Abstract

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 $s{t}_D(G)$ and is the minimum number of vertices whose removal changes the distinguishing number. We obtain a general upper bound $s{t}_D(G)⩽|V(G)|-D(G)+1$, and a relationships between the distinguishing stabilities of graphs $G$ and $G-v$, i.e., $s{t}_D(G)⩽s{t}_D(G-v)+1$, where $v\in V(G)$. Also we study the edge distinguishing stability number (distinguishing bondage number) of $G$.

10 pages, 3 figures