Graph automorphism

A bijection from a graph’s vertices to themselves that preserves adjacency and nonadjacency. Graph automorphisms capture the graph’s symmetries.

Graph automorphism group: The group of all automorphisms of a graph, with composition as its operation. Each adjacency-preserving permutation belongs to this group, whose structure records the graph’s symmetries.
Simple graph: An undirected graph with no loops or multiple edges. For simple graphs, preserving adjacency and nonadjacency characterizes automorphisms.
Graph isomorphism problem: The decision problem of determining whether two finite graphs are isomorphic. Automorphism groups provide structural information used by graph-isomorphism algorithms.
Graph endomorphism: A homomorphism from a graph to itself that preserves adjacency but need not be bijective. Unlike an automorphism, an endomorphism may collapse distinct vertices or fail to cover the graph.
Permutation group: A group whose elements are permutations of a set. Graph automorphisms are precisely the permutations that also preserve the graph’s structure.
Vertex (graph theory): A fundamental element of a graph, representing an object or position. An automorphism rearranges vertices while keeping the graph’s structure intact.
Graph canonization: The process of assigning isomorphic graphs the same canonical labeled representation. Understanding automorphisms helps identify equivalent labelings and the symmetries of canonical forms.
Graph homomorphism: A vertex map between graphs that sends adjacent vertices to adjacent vertices. Homomorphisms need not preserve nonadjacency or be bijections, unlike automorphisms.
Orbit-stabilizer theorem: A theorem relating an element’s orbit and stabilizer in a group action to the group’s order. It connects how automorphisms move a vertex to the subgroup that fixes it.
Adjacency matrix: A square matrix whose entries encode which pairs of graph vertices are adjacent. A vertex permutation is an automorphism exactly when it leaves this matrix unchanged under relabeling.

Linked from 6 pages