Graph isomorphism problem

The decision problem of determining whether two graphs are isomorphic: whether a bijection between their vertices preserves adjacency.

Graph isomorphism: A relation between graphs that holds when a vertex bijection preserves adjacency. The problem asks whether this relation holds for a given pair of graphs.
Graph automorphism problem: The decision problem of determining whether a graph has a nonidentity automorphism. It asks about symmetry within one graph rather than equivalence between two graphs.
Graph canonization: The task of assigning isomorphic graphs the same canonical labeled representation. A canonical form turns pairwise isomorphism tests into comparisons of representations.
Graph theory: The mathematical study of graphs, structures consisting of vertices joined by edges. Graph isomorphism compares the structure of two such objects.
P: The class of decision problems solvable by a deterministic algorithm in polynomial time. Whether graph isomorphism belongs to P remains unknown.
Certificate: A compact witness that allows a proposed answer to a decision problem to be checked efficiently. A vertex bijection is a polynomial-size certificate for a yes-instance.
Subgraph isomorphism problem: The problem of deciding whether one graph occurs as a subgraph of another. Allowing a graph to embed inside another makes the problem NP-complete.
D. G. Higman: A British mathematician whose work on permutation groups and graph symmetries influenced early isomorphism methods. Group-theoretic approaches connect graph isomorphism to permutation-group computation.
Bijection: A function that pairs every element of one set with exactly one element of another, and vice versa. An isomorphism must pair all vertices without omissions or collisions.
Babai's graph isomorphism algorithm: A 2016 algorithm that decides graph isomorphism in quasipolynomial time. It is the best-known general upper bound for the problem.

Linked from 4 pages