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.
-
