Regular graphs are the graphs in which the degree of each vertex is the same. The [Weisfeiler-Lehman algorithm](https://link.springer.com/chapter/10.1007/978-3-319-57586-5_22) fails to distinguish between the given two non-isomorphic regular graphs. 


Is there a fastest known algorithm for regular graph isomorphism? Are regular graphs the hardest instance for graph isomorphism? Is there any combinatorial or algebraic technique (group theoretic) to deal with this situation efficiently?



Are regular graphs the hardest instance for graph isomorphism?
The first place to look at is [E.M. Luks algorithm for polynomial GI for graphs of bounded degree](http://ieeexplore.ieee.org/abstract/document/4567803/?reload=true). The algorithm is group-theoretic, and utilizes the fact that subgroups of products of $S\_k$ for bounded $k$ always have subgroups of bounded index, which allows to divide-and-conquer over cosets of an automorphism subgraph stabilizer efficiently (since for bounded degree graphs it is contained within products of $S\_k$ induced by automorphisms of neighbourhoods of each vertex).


A [recent breakthrough of Babai](http://dl.acm.org/citation.cfm?id=2897542) solves GI in $\mathrm{exp}(O((\log n)^c))$ time. One of the main ideas (which is not particuraly novel to this paper) is that either the (primitive) quotient of an automorphism subgraph stabilizer either has subgroups of small index (which allows to apply the previous result), or contains an automorphism group of a large [Johnson scheme](https://en.wikipedia.org/wiki/Johnson_scheme). The paper then proceeds to treat the second case with an efficient symmetry-breaking procedure, which is novel and highly non-trivial.


It would probably be an overly simplified and very imprecise statement, but this implies that the hardest case for GI are graphs obtained from a [Johnson graph](https://en.wikipedia.org/wiki/Johnson_graph) in a non-trivial way.


More about regular graphs (as asked in OP): all hard cases are regular of course, but some regular graphs are more susceptible than others. One usual method of solving GI is to promote several vertices by giving them unique colors, and doing WL-refinement or other tricks; if promoting a small set allows to refine the most of the graph, then this graph is easy for GI. The majority of regular graphs are easy with respect to this approach. The Johnson graph is hard in the following sense: to reduce the size of the largest equivalence class of vertices below $cn$ for $c < 1$, we may need to promote $\Omega(n^{c'})$ vertices, which prevents the trivial "try all sets" method to work within reasonable time.


