A Graph Representative Structure for Detecting Automorphic Graphs

Abstract

Graphs are prevalently used to model the relationships between objects in various domains. Storing the graphs into large databases is a challenging task as it deals with efficient space and time management. Unlike item sets in huge transactional databases, it becomes essential to ensure the consistency of graph databases since relationships among edges of a graph are predominant. One of the necessary procedures required is a mechanism to check whether two graphs are automorphic(duplicated) or not. Difficulty in identifying and eliminating the automorphic graphs is a challenging problem to the research community. In this paper, we propose a graph representative structure that is called graph code. There are three main phases: preprocessing, code generation and code matching. In preprocessing phase, vertex list, edge list and adjacent edge information are generated for input graph. In code generation, edge dictionary plays an important role. The edge dictionary and adjacent edge information are used to generate graph codes. In code matching, the new graph code is compared with those of other graphs in graph dataset to determine whether they are automorphic or not. The experimental results and comparisons offer a positive response to the proposed structure.