MALAYSIAN MATHEMATICAL SCIENCES SOCIETY Methods of Destroying the Symmetries of a Graph

Abstract. A note v of a graph G is called fixed if every automorphism of G sends v onto itself. A graph or digraph or other graphical structure is then called fixed if every node is fixed, i.e., its automorphism group is the identity. We present several methods for fixing a graph (destroying its automorphisms). These may not work for all graphs. The methods include orienting some of the edges, coloring some of the nodes with one or more colors and the same for the edges, labeling nodes or edges, and adding or deleting nodes or edges. These considerations lead to a multitude of new invariants and open questions