TOPICS
Search

Canonical Labeling

A canonical labeling of a graph G is an ordering or renaming of its vertices that produces a distinguished labeled graph C(G) isomorphic to G. The resulting graph C(G) is a canonical form: two graphs are isomorphic exactly when their canonical forms are identical (McKay and Piperno 2014). The terminology is not uniform, and "canonical labeling" is sometimes also used for the resulting labeled graph. The complexity class of canonical labeling is not known.

Efficient canonical-labeling methods therefore yield efficient tests for isomorphic graphs. Important software implementations include nauty and Traces (McKay and Piperno 2014), bliss (Junttila and Kaski 2007), saucy, and conauto (McKay and Piperno 2014). In the Wolfram Language, canonical labeling is implemented by CanonicalGraph[g].

See also

Canonical Form, Graph Isomorphism, Isomorphic Graphs

Explore with Wolfram|Alpha

References

Junttila, T. and Kaski, P. "Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs." In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics (Ed. D. Applegate, G. S. Brodal, D. Panario, and R. Sedgewick). Philadelphia, PA: SIAM, pp. 135-149, 2007. https://doi.org/10.1137/1.9781611972870.13.McKay, B. "Practical Graph Isomorphism." Congr. Numer. 30, 45-87, 1981. https://users.cecs.anu.edu.au/~bdm/nauty/pgi.pdf.McKay, B. D. and Piperno, A. "Practical Graph Isomorphism, II." J. Symbolic Comput. 60, 94-112, 2014. https://doi.org/10.1016/j.jsc.2013.09.003.Piperno, A. "Search Space Contraction in Canonical Labeling of Graphs." 26 Jan 2011. https://arxiv.org/abs/0804.4881.

Referenced on Wolfram|Alpha

Canonical Labeling

Cite this as:

Weisstein, Eric W. "Canonical Labeling." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CanonicalLabeling.html

Subject classifications