Return to Question

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.

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.

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$.

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-

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) $$

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.

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).

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

Construction: $G$ is an $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$.

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 into 2 sub-graphs $C_y, D_y $.

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

So, $ D_{y-1} $ is a $t_{y-1}$ regular graph and can be divided/partitioned into 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 a maximum of $\log_2(|G|)$ times, using this dividing process recursively.

Matrix representation : $A$ is an adjacency matrix of an $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 graphs $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) $$

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.

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).

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).