**Motivation:** I am studying graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases required to get solution of graph isomorphism.

**Construction:**
$G$ is a $r$ regular graph, $k$ connected( not a complete or cycle graph).  A vertex of $G$ is $x_1$. 
All vertices which are not adjacent to $x_1$ create a sub-graph $C_1$.
  All vertices adjacent to $x_1$ create a sub-graph $, D_1 $. 
A vertex of $D_1$ is $x_2$. 

Using same method, based on adjacency of $x_2$ , $D_1$ can be divided. 

All vertices which are not adjacent to $x_2$ create a sub-graph $C_2$. 

All vertices adjacent to $x_2$ create a sub-graph $, D_2 $. 
    In general , $ D_{y-1} $ is a graph and can be divided/ partitioned  in to 2 sub graphs $C_y,  D_y $ .

At this stage, let me restrict the problem for simplicity of computation. Restrictions are-

1.	$C_y,  D_y $  are $s_y , t_y>0 $ regular graphs respectively for all iteration $y$

2.	$C_y,  D_y $  cannot be complete bipartite, complete graph or disjoint union of complete graphs.

So, $ D_{y-1} $ is a $t_{y-1}$ regular graph and can be devided/ partitioned  in to 2 sub graphs $C_y,  D_y $ . $C_y,  D_y $  are $s_y , t_y $ regular graphs respectively(given condition). 



 $G$ can be divided/ partitioned maximum $\log_2(|G|)$ times , using  this dividing process recursively .

**Matrix representation :** 
 A is an adjacency matrix of a   $r$-regular graph $G$. 
The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x_1 \in G$.
$A_x$ is the adjacency matrix of the graph $(G-x_1)$, where $C_1$ is the adjacency  matrix of the graph created by vertices which are not adjacent to $x_1$, and $D_1$ is the adjacency matrix of the graph created by vertices which are adjacent to $x_1$. $C_1,D_1$ are sub-graphs(regular) of graph $G$, $|C_1|>|D_1|$ where $|C_1|,|D_1|$ are total vertices number of graph $C_1,D_1$ respectively.
$$ A_x 
=
\left( \begin{array}{ccc}
C_1 & E_1  \\
E_1^{T} & D_1 \\
\end{array} \right) 
$$

again, this process can be done recursively, where $A_{y+1}=D_y$, $y=$ iteration number of the recursive process. 
$$ A_yx 
=
\left( \begin{array}{ccc}
C_y & E_y  \\
E_y^{T} & D_{y} \\
\end{array} \right) 
$$

$A_x$(=$A_1x$) is the matrix of 1st iteration, for 2nd iteration, $A$ matrix would be $A_2x$.

**Explanation for given restrictions:** 

1.	If any of $C_y,  D_y $  are not regular graphs  for iteration $y$, then $C_y $ or $ D_y $ can be divided into regular sub graphs where each sub graph has same valency.  It is well known, from  GI perspective, that , Irregular graph is easier to partition than regular graph  to determine  GI. So, if   irregular  $C_y , D_y $  will not increase search cases .

2.	$C_y,  D_y $  cannot be complete bipartite, complete or disjoint union of complete graphs because GI of these graph is easier, including them this partition method will increase the complexity, for the convenience of the next 'claim' , this restriction is  applied.



**Claim:**  
 *It is not possible to have an $E_y$ matrix as a zero matrix, i.e., it is not  possible to have disconnected sub-graphs $C_y,D_y$ under the given conditions  that $G$ is $k$ connected $r$ regular and $C_y , D_y$ are always regular(which are not complete bipartite, complete graph  nor disjoint union of complete graphs)  graphs in this recursive process.*

***Argument:*** see  http://mathoverflow.net/questions/211894/possibility-of-disconnected-subgraphs-of-a-k-connected-r-regular-graph-under?lq=1 and  http://mathoverflow.net/questions/212482/decomposition-of-a-regular-graph-and-connected-subgraphs?lq=1 this post.

**Question: Is it possible to partition a graph always as described above?**