On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach
<|reference_start|>On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a Counting Approach: 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.}<|reference_end|>
@article{arvind2007on,
    title={On Computing the Distinguishing Numbers of Planar Graphs and Beyond: a
  Counting Approach},
    author={V. Arvind, Christine T. Cheng, Nikhil R. Devanur},
    journal={arXiv preprint arXiv:math/0703927},
    year={2007},
    archivePrefix={arXiv},
    eprint={math/0703927},
    primaryClass={math.CO cs.DS}
}