Distinguishing Number

A labeling  of (the vertices) of a graph  with positive integers taken from the set  is said to be -distinguishing if no graph automorphism of  preserves all of the vertex labels. Formally,  is -distinguishing if for every nontrivial , there exists  such that , where  is the vertex set of  and  is the automorphism group of . The distinguishing number of  of  is then the smallest  such that  has a labeling that is -distinguishing (Albertson and Collins 1996).

Different graphs with the same automorphism group may have different distinguishing numbers.

 iff  is an identity graph. The distinguishing number of a graph  and its graph complement  are the same.

A graph  with  has distinguishing number  (Tymoczko 2005; due to Albertson, Collins, and Kleitman).

Special cases are summarized in the following table.

complete bipartite graph
complete graph
cycle graph
generalized Petersen graph
hypercube graph
path graph
star graph
-triangular graph
wheel graph

REFERENCES

Albertson, M. and Collins, K. "Symmetry Breaking in Graphs." Electronic J. Combinatorics 3, No. 1, R18, 17 pp., 1996.

 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r18.Konhauser, J. D. E.; Velleman, D.; and Wagon, S. Which Way Did the Bicycle Go? And Other Intriguing Mathematical Mysteries. Washington, DC: Math. Assoc. Amer., 1996.Rubin, F. Problem 729. In J. Recr. Math. 11, 128, 1979.

(Solution in Vol. 12, 1980).Tymoczko, J. "Distinguishing Numbers for Graphs and Groups." 17 Mar 2005. http://arxiv.org/abs/math/0406542