Stochastic Modeling and Applied Research of Technology



Graph Theory
Edge connectivity
Spectral Graph Theory
Symmetric matrix

How to Cite

Garimella, R. (2023). Necessary conditions for graph isomorphism problem: polynomial time algorithms. Stochastic Modeling and Applied Research of Technology, 3, 36-44.


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.
Creative Commons Attribution License Logo

This work is licensed under a Creative Commons Attribution 4.0 International License.