TY - JOUR
AU - Garimella, Ramamurthy
PY - 2023
Y1 - 2023/12/18
TI - Necessary conditions for graph isomorphism problem: polynomial time algorithms
JF - Stochastic Modeling and Applied Research of Technology
JA - SMARTY
VL - 3
DO - 10.57753/SMARTY.2023.10.52.005
UR - http://smarty.karelia.website/article/3/5/
SP - 36
LP - 44
SN - 2782-4705
AB - 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.
ER -