A New Polynomial Invariant for Graph Isomorphism via Bipartite Double Cover Vertex Covers and Clique Profile

Abstract

We introduce a new polynomial-time graph invariant combining three complementary components: (1) the enriched Bipartite Double Cover (BDC) vertex cover signature; (2) the Laplacian eigenvalue spectrum; and (3) the K_4 clique profile and Ollivier-Ricci curvature. We demonstrate that while spectral and standard BDC methods collapse on strongly regular graphs (SRGs) due to extreme symmetry, the geometric and dense-topological components of this hybrid invariant break the cospectrality. Specifically, the invariant successfully discriminates the classical cospectral pair Shrikhande vs. Rook(4,4) [SRG(16,6,2,2)] in polynomial time, where Shrikhande is K_4-free and Rook(4,4) contains exactly 8 cliques. Furthermore, empirical validation on low-power ARM Edge hardware demonstrates that the invariant scales efficiently, processing dense Paley graphs (up to N=97) in under 5 milliseconds. This confirms its sub-millisecond viability for real-time edge computing, zero-knowledge proofs (ZKPs) cryptanalysis, and cheminformatics.