Graph Isomorphisms

Abstract

A graph is a mathematical object consisting of a vertex set related by an edge set. For two graphs to be considered isomorphic there must be a one to one mapping of their vertex sets onto the other that preserves adjacency. The graph isomorphism problem has a long history of study of heuristic methods and algorithmic solutions. Particularly concerning much larger graphs, it has been useful to examine how traits of different types of subgraphs allow for easier comparisons. In this manner, algorithms for determining whether certain types of graphs are isomorphic have been developed. However not all cases are so simple, so the problem's complexity class remains uncertain. The many advancements made in the study of graph isomorphisms have created a deeper understanding of different areas of study in both mathematics and computer science. This paper will review some of the existing methods and the history of research into the problem.