On Isomorphism Testing In \(3\)-Regular Graphs

The polynomial algorithms for isomorphism testing in \(3\)-regular graphs known to date use set-wise stabilisation in \(2\)-groups acting on singletons, pairs, and sometimes triples of vertices. In this note we describe a new, simpler way of “getting rid of the triples”. Although the order of the complexity of isomorphism testing remains \(O(\text{n}^3 \log \text{n})\), the resulting algorithm is more efficient, since this portion of the set-wise stabilisation in the algorithm will be faster.