# Graph isomorphism

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

An equivalence relation on the set of graphs. An isomorphic mapping of a non-oriented graph to another one is a one-to-one mapping of the vertices and the edges of one graph onto the vertices and the edges, respectively, of the other, the incidence relation being preserved. Two graphs are said to be isomorphic if there exists an isomorphic mapping of one of these graphs to the other. In the figure, the graphs and are not isomorphic, whereas the graphs and are isomorphic. Isomorphic graphs are usually not distinguished from one another. The number of pairwise non-isomorphic graphs with a given number of vertices and a given number of edges is finite. Isomorphism of oriented graphs, hypergraphs and networks can be defined in a similar manner.

Figure: g044950a

Figure: g044950b

Figure: g044950c

The problem of establishing an isomorphism between graphs is an important problem in graph theory. There are algorithms for certain classes of graphs with the aid of which isomorphism can be fairly effectively recognized (e.g. for trees, cf. Tree, or planar graphs, [1]). Certain classes of graphs with vertices have been proved to be uniquely reconstructible (up to an isomorphism) from the set of subgraphs of it with vertices obtained by removing the vertex in all possible ways. This has been established, in particular, for trees and tournaments (for , cf. Tournament)

#### References

 [1] J.E. Hopcroft, R.E. Tarjan, "Isomorphism of planar graphs" R.E. Miller (ed.) J.W. Tatcher (ed.) , Complexity of Computer Computations. Proc. Symp. IBM , Plenum (1972) pp. 131–152; 187–212 [2] P.J. Kelly, "A congruence theorem for trees" Pacific J. Math. , 7 (1957) pp. 961–968