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 Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition and Decomposition of a regular graph and connected subgraphs this post.

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