An Efficient Structural Descriptor Sequence to Identify Graph Isomorphism and Graph Automorphism

Abstract

In this paper, we study the graph isomorphism and graph automorphism problems. We propose a novel technique to analyze graph isomorphism and graph automorphism. Further we handled some strongly regular datasets for prove the efficiency of our technique. The neighbourhood matrix $\mathcal{N}\mathcal{M}(G)$ was proposed in \cite {ALPaper} as a novel representation of graphs and was defined using the neighbourhood sets of the vertices. It was also shown that the matrix exhibits a bijection between the product of two well known graph matrices, namely the adjacency matrix and the Laplacian matrix. Further, in a recent work\cite{NM_SPath}, we introduced the sequence of matrices representing the powers of $\mathcal{N}\mathcal{M}(G)$ and denoted it as ${\mathcal{N}\mathcal{M}}^{\{l\}},1\le l\le k(G)$ where $k(G)$ is called the \textbf{iteration number}, $k(G)=\ceil*{\log_{2}diameter(G)} $. In this article we introduce a structural descriptor given by a sequence and clique sequence for any undirected unweighted simple graphs with help of the sequences of matrices $N{M}^{\{l\}}$. The $i^{th}$ element of structural descriptor sequence encodes the complete structural information of the graph from the vertex $i\in V(G)$. The $i^{th}$ element of clique sequence encodes the Maximal cliques on $i$ vertices. The above sequences is shown to be a graph invariants and is used to study the graph isomorphism and automorphism problem.

19 pages