Counting Walks - a Novel Approach to the Graph Isomorphism Problem

Abstract

This paper presents the concept of walk-labeling that can be used to decide the graph isomorphism problem in polynomial time combinatorially under certain conditions - which hold for a wide range of the graph pairs. It turns out that all non-cospectral graph pairs can be differentiated with a combinatorial method, furthermore, even if the graphs are cospectral and nonisomorphic, they might be distinguished by combinatorially verifying certain properties of their eigenspaces. Strong walk-labeling, a strengthening of the aforementioned labeling, has also been introduced for practical purposes. Its applications include speeding up any backtracking graph matching algorithm, and the generation of graph fingerprints, which identify all the graphs uniquely it was tested on, including all known strongly regular graphs. To practically evaluate the new methods, tests have been carried out on biological, strongly regular and random graph.