Graph isomorphism

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H Graph isomorphism_sentence_0

such that any two vertices u and v of G are adjacent in G if and only if f(u) and f(v) are adjacent in H. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection. Graph isomorphism_sentence_1

Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. Graph isomorphism_sentence_2

A set of graphs isomorphic to each other is called an isomorphism class of graphs. Graph isomorphism_sentence_3

The two graphs shown below are isomorphic, despite their different looking drawings. Graph isomorphism_sentence_4

Graph isomorphism_table_general_0

Graph isomorphism_cell_0_1_0 Graph isomorphism_cell_0_1_1 f(a) = 1

f(b) = 6 f(c) = 8 f(d) = 3 f(g) = 5 f(h) = 2 f(i) = 4 f(j) = 7Graph isomorphism_cell_0_1_2

Variations Graph isomorphism_section_0

In the above definition, graphs are understood to be uni-directed non-labeled non-weighted graphs. Graph isomorphism_sentence_5

However, the notion of isomorphic may be applied to all other variants of the notion of graph, by adding the requirements to preserve the corresponding additional elements of structure: arc directions, edge weights, etc., with the following exception. Graph isomorphism_sentence_6

Isomorphism of labeled graphs Graph isomorphism_section_1

For labeled graphs, two definitions of isomorphism are in use. Graph isomorphism_sentence_7

Under one definition, an isomorphism is a vertex bijection which is both edge-preserving and label-preserving. Graph isomorphism_sentence_8

Under another definition, an isomorphism is an edge-preserving vertex bijection which preserves equivalence classes of labels, i.e., vertices with equivalent (e.g., the same) labels are mapped onto the vertices with equivalent labels and vice versa; same with edge labels. Graph isomorphism_sentence_9

The second definition is assumed in certain situations when graphs are endowed with unique labels commonly taken from the integer range 1,...,n, where n is the number of the vertices of the graph, used only to uniquely identify the vertices. Graph isomorphism_sentence_10

In such cases two labeled graphs are sometimes said to be isomorphic if the corresponding underlying unlabeled graphs are isomorphic (otherwise the definition of isomorphism would be trivial). Graph isomorphism_sentence_11

Motivation Graph isomorphism_section_2

The formal notion of "isomorphism", e.g., of "graph isomorphism", captures the informal notion that some objects have "the same structure" if one ignores individual distinctions of "atomic" components of objects in question. Graph isomorphism_sentence_12

Whenever individuality of "atomic" components (vertices and edges, for graphs) is important for correct representation of whatever is modeled by graphs, the model is refined by imposing additional restrictions on the structure, and other mathematical objects are used: digraphs, labeled graphs, colored graphs, rooted trees and so on. Graph isomorphism_sentence_13

The isomorphism relation may also be defined for all these generalizations of graphs: the isomorphism bijection must preserve the elements of structure which define the object type in question: arcs, labels, vertex/edge colors, the root of the rooted tree, etc. Graph isomorphism_sentence_14

The notion of "graph isomorphism" allows us to distinguish graph properties inherent to the structures of graphs themselves from properties associated with graph representations: graph drawings, data structures for graphs, graph labelings, etc. For example, if a graph has exactly one cycle, then all graphs in its isomorphism class also have exactly one cycle. Graph isomorphism_sentence_15

On the other hand, in the common case when the vertices of a graph are (represented by) the integers 1, 2,... N, then the expression Graph isomorphism_sentence_16

may be different for two isomorphic graphs. Graph isomorphism_sentence_17

Whitney theorem Graph isomorphism_section_3

Main article: Whitney graph isomorphism theorem Graph isomorphism_sentence_18

The Whitney graph isomorphism theorem, shown by Hassler Whitney, states that two connected graphs are isomorphic if and only if their line graphs are isomorphic, with a single exception: K3, the complete graph on three vertices, and the complete bipartite graph K1,3, which are not isomorphic but both have K3 as their line graph. Graph isomorphism_sentence_19

The Whitney graph theorem can be extended to hypergraphs. Graph isomorphism_sentence_20

Recognition of graph isomorphism Graph isomorphism_section_4

Main article: Graph isomorphism problem Graph isomorphism_sentence_21

While graph isomorphism may be studied in a classical mathematical way, as exemplified by the Whitney theorem, it is recognized that it is a problem to be tackled with an algorithmic approach. Graph isomorphism_sentence_22

The computational problem of determining whether two finite graphs are isomorphic is called the graph isomorphism problem. Graph isomorphism_sentence_23

Its practical applications include primarily cheminformatics, mathematical chemistry (identification of chemical compounds), and electronic design automation (verification of equivalence of various representations of the design of an electronic circuit). Graph isomorphism_sentence_24

The graph isomorphism problem is one of few standard problems in computational complexity theory belonging to NP, but not known to belong to either of its well-known (and, if P ≠ NP, disjoint) subsets: P and NP-complete. Graph isomorphism_sentence_25

It is one of only two, out of 12 total, problems listed in whose complexity remains unresolved, the other being integer factorization. Graph isomorphism_sentence_26

It is however known that if the problem is NP-complete then the polynomial hierarchy collapses to a finite level. Graph isomorphism_sentence_27

In November 2015, László Babai, a mathematician and computer scientist at the University of Chicago, claimed to have proven that the graph isomorphism problem is solvable in quasi-polynomial time. Graph isomorphism_sentence_28

As of November 2015, this work has not yet been vetted. Graph isomorphism_sentence_29

In January 2017, Babai briefly retracted the quasi-polynomiality claim and stated a sub-exponential time time complexity bound instead. Graph isomorphism_sentence_30

He restored the original claim five days later. Graph isomorphism_sentence_31

Its generalization, the subgraph isomorphism problem, is known to be NP-complete. Graph isomorphism_sentence_32

The main areas of research for the problem are design of fast algorithms and theoretical investigations of its computational complexity, both for the general problem and for special classes of graphs. Graph isomorphism_sentence_33