Rui Xue
Published 2023-05-22Version 1
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 $\mathtt{P}$.
Testing isomorphism of circulant objects in polynomial time
Recognizing and testing isomorphism of Cayley graphs over an abelian group of order $4p$ in polynomial time
Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time
![QR code for arXiv:2305.12688 [math.CO]](http://oss.arxitics.com/images/favicon.svg)