TOPICS
Search

Distinguishing Number


A labeling phi of (the vertices) of a graph G with positive integers taken from the set {1,2,...,r} is said to be r-distinguishing if no graph automorphism of G preserves all of the vertex labels. Formally, phi is r-distinguishing if for every nontrivial sigma in Aut(G), there exists x in V(G) such that phi(x)!=phi(xsigma), where V(G) is the vertex set of G and Aut(G) is the automorphism group of G. The distinguishing number of D(G) of G is then the smallest r such that G has a labeling that is r-distinguishing (Albertson and Collins 1996).

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

D(G)=1 iff G is an identity graph. The distinguishing number of a graph G and its graph complement G^_ are the same.

A graph G with |Aut(G)|<=k! has distinguishing number D(G)<=k (Tymoczko 2005; due to Albertson, Collins, and Kleitman).

Special cases are summarized in the following table.


See also

Chromatic Number, Chromatic Polynomial

Explore with Wolfram|Alpha

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

Cite this as:

Weisstein, Eric W. "Distinguishing Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DistinguishingNumber.html

Subject classifications