Tyshkevich's Graph Decomposition and the Distinguishing Numbers of Unigraphs

A $c$-labeling $\phi :V(G)\to \{1,2,\text{hdots},c\}$ of graph $G$ is distinguishing if, for every non-trivial automorphism $\pi$ of $G$, there is some vertex $v$ so that $\phi (v)\mathrm{\ne }\phi (\pi (v))$. The distinguishing number of $G$, $D(G)$, is the smallest $c$ such that $G$ has a distinguishing $c$-labeling. We consider a compact version of Tyshkevich’s graph decomposition theorem where trivial components are maximally combined to form a complete graph or a graph of isolated vertices. Suppose the compact canonical decomposition of $G$ is $G_k\circ G_{k-1}\circ \cdots \circ G_1\circ G_0$. We prove that $\phi$ is a distinguishing labeling of $G$ if and only if $\phi$ is a distinguishing labeling of $G_i$ when restricted to $V(G_i)$ for $i=0,\text{hdots},k$. Thus, $D(G)=\max \{D(G_i),i=0,\text{hdots},k\}$. We then present an algorithm that computes the distinguishing number of a unigraph in linear time.