2023/05/22 by Rui Xue, Xue, Rui
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2305.12688
openalex publication_date 2023/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G, the graph [G] obtained by adding, for each pair of vertices of G, a unique vertex adjacent to both vertices is called the binding graph of G. In this work, we show that the class of binding graphs is graph-isomorphism complete and that the stable partitions of binding graphs by the Weisfeiler-Lehman (WL) algorithm produce automorphism partitions. To test the isomorphism of two graphs G and H, one computes the stable graph of the binding graph [G\uplus H] for the disjoint union graph G\uplus H. The automorphism partition reveals the isomorphism of G and H. Because the WL algorithm is a polynomial-time procedure, the claim can be made that the graph-isomorphism problem is in complexity class \mathttP.