Methods of Destroying the Symmetries of a Graph
Frank Harary · 2001
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. If a graph already has the identity group, then it is fixed. If not, then fixing a graph G means altering it in some way to obtain a fixed graphical structure. The first published method of fixing a graph is apparently due to Tutte (13). He applied his procedure to planar graphs only. He selected an arbitrary edge of the graph, oriented it in one of the two possible ways, and then drew at the center of the selected edge a small arrow perpendicular to the edge, oriented in one of the two possible directions. This served to fix the planar graph. The purpose of the small arrow was to specify the exterior region of the graph. Tutte's objective was to count triangulations of the plane without having to take their symmetries into consideration. Our purpose is to present an exposition of several methods of fixing a graph: 1. Some graphs can be fixed by orienting a subset of its edges. This is not true of all