Tyshkevich's Graph Decomposition and the Distinguishing Numbers of Unigraphs

Abstract

A $c$-labeling $ϕ: V(G) \rightarrow \{1, 2, \hdots, c \}$ of graph $G$ is distinguishing if, for every non-trivial automorphism $\pi$ of $G$, there is some vertex $v$ so that $\varphi (v)\ne \varphi (\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 $\varphi$ is a distinguishing labeling of $G$ if and only if $\varphi$ is a distinguishing labeling of $G_i$ when restricted to $V(G_i)$ for $i = 0, \hdots, k$. Thus, $D(G) = \max \{D(G_i), i = 0, \hdots, k \}$. We then present an algorithm that computes the distinguishing number of a unigraph in linear time.

arXiv comment22 pages plus an appendix with 8 pages