A New and Efficient Framework for the Graph Isomorphism Problem

This paper provides a new framework to study graph structure. It enables us to define graph orthogonality and a new metrics on graphs. Furthermore, it enables us to define the coordinate representation of graphs with respect to an ordered set of graphs, which benefits us in the graph isomorphism problem. If any graph of set $A$ has a unique coordinates with respect to a graph set $ B$, then, we call $B$ is a basis for the graphs set $A$. Having a basis, any graph finds a unique coordinates. Thus, the graph isomorphism problem equals to comparison of the coordinates. This fact provides a formal approach to study the computational complexity of the graph isomorphism problem, i.e. finding a suitable basis. We have shown that graphs on at most 3log(n) vertices make a basis for almost every $n$-vertex graphs. This fact, easily, results that graph isomorphism problem can be solved in $\exp(6\log^2(n))$ time for almost every pair of $n$-vertex graphs.