Structural Relationship of Isomorphic Graph and its Mapping to Hamming Distance

^1,2,3 Department of Computer Science, APS University, Rewa, 486003 M.P., India
⁴ Velocis Systems Pvt. Ltd. A-25, Sector-67, Noida - 201301, Uttar Pradesh, India

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Published online: 20 November 2025

Abstract

Mapping graph isomorphism to Hamming distance enables a simple yet effective approach to quantifying structural similarity. By encoding graphs as binary adjacency vectors—flattened from the upper triangle of the adjacency matrix—structural comparisons can be performed using Hamming distance, a well-established metric in information theory. Isomorphic graphs yield a Hamming distance of zero, under the correct vertex permutation, while non-isomorphic graphs exhibit nonzero distances reflecting structural differences. A case study illustrates this concept, revealing a Hamming distance of two between two sample graphs, corresponding to two differing adjacencies. The method provides a computationally efficient alternative to traditional graph edit distance, especially for small perturbations or approximate isomorphism detection. Applications extend network robustness assessment, also molecular structure comparison in chemoinformatics, and error detection in noisy or incomplete graph data. graph neural networks (GNNs) is compatible with the binary encoding format, supporting integration with learning-based models. Future extensions' goal is to support weighted and labelled graphs, improve scalability, and enhance robustness in dynamic or large-scale graph analysis.