Destroying automorphisms by fixing nodes

AbstractThe fixing number of a graph G is the minimum cardinality of a set S⊂V(G) such that every nonidentity automorphism of G moves at least one member of S, i.e., the automorphism group of the graph obtained from G by fixing every node in S is trivial. We provide a formula for the fixing number of a disconnected graph in terms of the fixing numbers of its components and make some observations about graphs with small fixing numbers. We determine the fixing number of a tree and find a necessary and sufficient condition for a tree to have fixing number 1