A vertex $k$-labeling of graph $G$ is distinguishing if the only automorphism that preserves the labels of $G$ is the identity map. The distinguishing number of $G$, $D(G)$, is the smallest integer $k$ for which $G$ has a distinguishing $k$-labeling. In this paper, we apply the principle of inclusion-exclusion and develop recursive formulas to count the number of inequivalent distinguishing $k$-labelings of a graph. Along the way, we prove that the distinguishing number of a planar graph can be computed in time polynomial in the size of the graph.

PDF file

In: SIAM Journal on Discrete Mathematics

Publisher: Society for Industrial and Applied Mathematics
Copyright © 2007 by Society for Industrial and Applied Mathematics.

Details