Objective : To find a set of permutations for a irregular graph which is also a set of automorphism. This finding process uses permutations of 2 regular subgraphs of the given graph.
Description and Notation :
$G$ is an irregular graph, $k$ connected( not a complete , cycle graph).$\alpha$ is the set of permutations of $G$ (it has all automorphism).
$G$ has 2 kinds of vertices, vertices of $r_1$ degree which create a $t_1$ regular sub graph $C$ and vertices of $r_2$ degree which create a $t_2$ regular sub graph $D$.
$C,D$ are not complete /cycle graph.
$C_1, D_1,A_x$ are matrices of graphs $C,D,G$ respectively .
$$ A_x = \left( \begin{array}{ccc} C_1 & E_1 \\ E_1^{T} & D_1 \\ \end{array} \right) $$
$\alpha_1 , \alpha_2 $ are the set of permutations of $C_1 , D_1$ respectively. $\alpha_1 , \alpha_2 $ include all possible permutations needed for automorphism of $C_1 , D_1$. Given, each of $\alpha_1 , \alpha_2 $ has $T(m)\leq m^{log_2(m)}$ permutations / elements.
Process: To find an element of $\alpha$, try each possible $(P_1,P_2)$ where $P_1 \in \alpha_1; P_2 \in \alpha_2 $ .
It is required to check whether $E_1,C_1,D_1$ are unchanged or not for each possible $(P_1,P_2)$. lets define set $\alpha_3$ which has all possible $(P_1,P_2)$ for which $E_1,C_1,D_1$ are unchanged.
Questions :
1) Is this a correct process / algorithm to find all elements of $\alpha$ from $(P_1,P_2)$ where $P_1 \in \alpha_1; P_2 \in \alpha_2 $, i.e. $\alpha_3$ has all elements of $\alpha$?
2) Complexity of this process/ algo: is $ T^2(m)$ (time complexity), Is this a correct estimation?
Thanks, Please inform if anything is unclear/ undefined .
You are correct that any automorphism of $G$ must stabilize both subgraphs $C$ and $D$. So let's say that $C$ has $c$ vertices and $D$ has $d$ vertices. So you can find automorphism groups of $C$ and $D$, then if $a_{1}$ is an automorphism of $c$ and $a_{2}$ is an automorphism of $D$, you can test if $a_{1}a_{2}$ is an automorphism of $G$.
A (very inefficient but I don't know better offhand) way to find the automorphism group of $C$ is to test permutations. Lets say $C_{1}$ is the matrix of the graph $C$, and $g$ is a permutation of $\{1,2,\ldots,c\}$. We convert $g$ to a permutation matrix $G$, then test whether $G C_{1} G^{T} = C_{1}$. If so, then $g$ is an automorphism of $C_{1}$ (and so are all powers of $g$).
As you find automorphisms, all products of automorphisms are again automorphisms, so it can be tricky to be smart about which permutations you test and in what order (you don't necessarily want to test every permutation, but at the same time it can be computationally expensive to determine which permutations you don't need to test). Hopefully someone smarter than me can chip in on better algorithms.
Now, once you have automorphism groups of $C$ and $D$, you are not guaranteed that $g_{1} \in \alpha_{1}$, $g_{2} \in \alpha_{2}$ implies that $g_{1}g_{2} \in \alpha$; you need to test that $\begin{bmatrix} G_{1} & 0\\0 &G_{2} \end{bmatrix} \begin{bmatrix} C_{1} & E_{1}^{T}\\E_{1} & D_{1} \end{bmatrix} \begin{bmatrix} G_{1}^{T} & 0\\0&G_{2}^{T} \end{bmatrix} = \begin{bmatrix}C_{1}&E_{1}^{T}\\E_{1}&D_{1}\end{bmatrix}$.