Abstract

In this research paper, it is proved that two arbitrary graphs are isomorphic only if the quadratic forms associated with the two adjacency matrices are same(upto reordering the monomials). Based on the proof, a polynomial time algorithm is designed for testing necessary condition for isomorphism of graph (i.e. effectively deciding whether two graphs are isomorphic). The algorithm requires O(N^3) comparison operations. Also, a polynomial time algorithm for checking necessary condition on whether two graphs are isomorphic is designed under the condition that the associated adjacency matrices are non-singular and are related through a symmetric permutation matrix. The algorithms are essentially based on linear algebraic concepts related to graphs. Also, some new results in spectral graph theory are discussed.