A Method for Detecting Isomorphism in Graphs Using Vertex Degree Correspondence With Partitioning
D. B. Warnaar, Meng-Sang Chew, Stephan Olariu · 1992
Abstract An efficient and accurate procedure is presented for testing pairs of graphs for isomorphism. The procedure determines isomorphism conclusively by partitioning the graphs into sets of vertices of the same degree. Subsequently, isomorphism is proven or disproven through a comparison of the inter-connectivity of the vertices within each set and a comparison of the inter-connectivity between each set. The procedure is tested on large sets of graphs generated using a (novel) technique also introduced in this article. The procedure has shown to be more efficient than previous methods, without compromising its accuracy.