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

**Construction:**
$G$ is a $r$ regular graph, $k$ connected( not a complete , 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 graph (utility graph), 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_x$ matrix would be $A_2x$.

**How restrictions can be lifted later:** 

1.	If  $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(utility graph), complete or disjoint union of complete graphs but GI of these graphs are easier.

 ***Both conditions can be lifted .***



**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?** 

**Edition 1 :** V.A.Taskinov, Regular subgraphs of regular graphs. Sov.Math.Dokl.26(1982), 37-38 .
In this paper he proved the following : Let $0<k<r$ be positive odd integers. Then every $r$-regular graph contains a $k$-regular subgraph (Here, the graph need not be simple).