Graph isomorphism near isomorphism a study for networks and molecular structures

Abstract

Algorithm complexities of Graph Isomorphism checking Exact Graph Matching procedures directly depend on the order and size of the graphs and take exponential time complexity In this research work, investigations are carried out so as to find chances to reduce the algorithmic complexities for Graph Isomorphism problem from exponential to possibly near polynomial or similar time Graphs are represented in a mathematical subspace such that two isomorphic graphs will have the same mathematical representation Every connected unweighted graph is given a unique mathematical representation of fixed size This representation is devised based upon the vertex influence proliferation of each vertex towards its neighbours It embeds the topological properties of the graph in particular vertex influence towards its neighbours Using this graph representation similarity scores between graphs are computed that ranges between 0 and 1 inferring 1 for high similarity Isomorphic graphs always have similarity score as 1 whereas the converse is not necessarily true newline