Graph automorphism

In graph theory, mathematicians study structures made of vertices and edges. An automorphism is a specific type of symmetry within these graphs. It occurs when a graph is mapped onto itself while preserving all connectivity. This means the connections between vertices must stay exactly the same. If two vertices form an edge before the mapping, they must form an edge after the mapping. This process is a permutation of the vertex set. Essentially, an automorphism is a graph isomorphism from a graph to itself. This concept applies to both directed and undirected graphs.

When we look at these symmetries, we see they follow strict mathematical rules. If you perform one automorphism and then another, the result is also an automorphism. This is called composition. Because of this, the set of all automorphisms for a specific graph forms a mathematical structure called a group. This is known as the automorphism group of the graph. A famous discovery by mathematician Robert Frucht relates these groups to graphs. Frucht's theorem states that all groups can be represented as the automorphism group of a connected graph. He specifically showed this is possible even with a cubic graph.

Graphs can be classified by how much symmetry they possess. An asymmetric graph is an undirected graph that has only the trivial automorphism. This means there is no way to move the vertices to create a new look. Other graphs are highly regular. A vertex-transitive graph allows any vertex to be mapped to any other vertex. An edge-transitive graph allows any edge to be mapped to any other edge. Some graphs are even more balanced, known as symmetric graphs. In these, every pair of adjacent vertices can be mapped to any other pair of adjacent vertices.

There are even more specialized categories of symmetry. A distance-transitive graph allows any two vertices to be mapped to any other pair that shares the same distance. Some graphs are semi-symmetric, meaning they are edge-transitive but not vertex-transitive. Half-transitive graphs are both vertex-transitive and edge-transitive, but they are not symmetric. Directed graphs can also be skew-symmetric. In a skew-symmetric graph, a permutation maps edges to edges but reverses their direction. This permutation must also be an involution, meaning it is its own inverse.

Calculating these symmetries is a complex task for computers. The problem of finding the automorphism group is linked to the graph isomorphism problem. This problem is known to belong to the complexity class NP. However, it is not known if it is in P or if it is NP-complete. It may actually be NP-intermediate. Finding if a graph has any nontrivial symmetries is called the graph automorphism problem. While no general polynomial-time solution exists, algorithms work well for graphs where vertex degrees are bounded by a constant.

Scientists use several software tools to handle these complex calculations. Tools like NAUTY and BLISS are widely used. BLISS and NAUTY can also produce something called a canonical labeling. Another tool, SAUCY, is optimized specifically for solving graph automorphism. SAUCY is extremely efficient for sparse graphs. It can process graphs containing millions of vertices in only a few seconds. For a graph with n vertices, the automorphism group can be described using no more than n squared generators.

Understanding graph automorphisms has many practical uses in the real world. It is very helpful for graph drawing and visualization tasks. Researchers use these symmetries to create drawings where the graph's balance is visible. This can be done by identifying symmetries to guide where vertices are placed. In chemistry, molecular symmetry can predict or explain how chemicals behave. It is also used in formal verification and logistics to solve structured instances of Boolean Satisfiability.