# Some doubts on the algorithm of graph isomorphism of bounded degree graph

There is an well known algorithm given by E.M Luks for bounded graph isomorphism. There are three important steps of the algorithm two of them are given below:

1. If the group action on vertex set of input graph is transitive (single orbit) then solve the isomorphism problem in each coset:

$$ISO(G,X,Y) = ISO(K_i\sigma_1,X,Y) \cup ISO(K_i\sigma_2,X,Y)\cdots ISO(K_i\sigma_k,X,Y)$$

where $$k$$ is number of cosets. The $$K_i$$ is a kernel of group action $$\pi : G \times B \mapsto B$$.

1. If the group action on vertex set of input graph is not transitive and let $$B_1,B_2,\cdots B_l$$ are the orbits (see group action $$\pi$$). Then we solve problem in each orbit : $$ISO_B(K_i\sigma_1,X,Y)=ISO_{B_{1}} (ISO_{B_{2}}\cdots ISO_{B_l}(K_i\sigma_1))$$

Questions :

1. From step we will be getting the solutions , but how to patch these all solutions to get a solution to original problem.

2. In step set $$B = \{B_1,B_2, \cdots, B_l\}$$ is a collection of orbits , If $$B$$ is a minimal system of imprimitivity then (step 2) still works or not.

• Question 2 is very unclear. $B$ is a set of sets, how can it be a collection of partitions? Each $B_i$ is stabilized by $G$, hence $B$ is obviously $G$-invariant. Please clarify your question. Further, note that $G$ doesn't act on the set of vertices but on the collection of subsets of vertices (see the definition of $A$ in the original paper). Oct 20, 2017 at 17:04
• @ Mikhail Tikhomirov I have edited the question Oct 20, 2017 at 17:42

1. We know that each $ISO$ is either a coset or an empty set. Suppose that non-empty answers to children $ISO$'s are cosets $g_i H_i$. Take $g_1$ as a representative for the resulting coset, then the subgroup $H$ corresponding to the resulting coset is induced by $g_1^{-1}g_i h_i$, where $h_i$ ranges over generators of $H_i$.
• This note refers to the fact that $K_i$ stabilizes each block, hence the next step after splitting $G$ into cosets will always be the intransitive step. Oct 21, 2017 at 7:47