= Canonical graph labeling
= Graph canonical labeling
{synonym}
\b[Canonical graph labeling] computes a standardized labeled representative of a <graph>, with a fixed convention that assigns identical representatives exactly to <isomorphic graphs>. For finite graphs, a labeling is a <bijection> from the original vertices to a standard set such as $\{1,\ldots,n\}$. A canonicalization procedure chooses a representative adjacency structure, not simply the order in which vertices happened to be supplied.
One explicit convention labels a finite undirected <simple graph> in every possible way and chooses the lexicographically least upper-triangular <adjacency matrix> string. The article <complete graph invariant> proves that this representative, together with vertex count, determines the graph up to <graph isomorphism>. Efficient software seeks the same kind of isomorphism-invariant representative without literally enumerating every permutation. The authors' nauty and Traces project identifies canonical labeling and graph-automorphism computation as supported tasks.<nauty and Traces by Brendan McKay and Adolfo Piperno>[project overview and Documentation]{ref}
An original three-vertex path makes a subtle distinction visible. In the edge-string order $(12,13,23)$, the least string is $011$. It puts the central vertex at label3 and the two leaves at labels1and2. Either assignment of the two original leaves gives the same canonical adjacency matrix. The representative is fixed, while the map from original vertices to labels need not be unique.
This ambiguity is forced by <graph automorphisms>. If an automorphism exchanges two indistinguishable vertices, no injective vertex-naming rule can both remain unchanged by that exchange and give the two vertices different names. More formally, requiring $\ell(\alpha(v))=\ell(v)$ for every automorphism $\alpha$ forces $\alpha(v)=v$ whenever $\ell$ is injective. A graph with a nontrivial automorphism therefore cannot have fully symmetry-invariant distinct names for all original vertices.
Canonical graph labeling instead requires the resulting labeled graph to be invariant under relabeling of the input. A returned vertex permutation may select one among equivalent choices. For a triangle, all six labelings give the same adjacency matrix, while six different input-to-label maps remain possible.
Vertex colors, directed edges or other attributes must be included in the structure if the desired isomorphisms are to preserve them. Comparing outputs from different canonicalization conventions or program options also needs care: identical invariance goals do not require every implementation to choose the same representative.
Back to article page
