# Partitioning graph for Graph Isomorphism

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

Partition method: $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$.

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

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

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.

Question: how a graph can be constructed so that the graph has regular subgraph 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).

• Your conditions indicate that your graph is strongly regular. If C1 and D1 have the same properties, then you have a highly restricted class of strongly regular graphs, see sciencedirect.com/science/article/pii/002186937890220X . It is most unlikely that such graphs are the hardest graphs for the isomorphism problem. – Brendan McKay Jul 29 '15 at 2:52
• @vzn The existing practical approaches have trouble when there are inequivalent vertices that are hard to distinguish. Regularity is a step in that direction but not enough by itself. On the other hand, very restricted classes of graphs often allow specially tailored treatment. Nobody really knows how to define the "hardest" class of graphs. – Brendan McKay Aug 1 '15 at 2:05
• @Jim, Nobody knows. However it is interesting that the fastest known algorithm for strongly regular graphs is faster than the fastest known for general graphs, see ieeexplore.ieee.org/xpl/… – Brendan McKay Aug 1 '15 at 3:36
• The strongly regular graph on 416 vertices described in this paper arxiv.org/abs/1305.2584 has a property similar to what is discussed here. – Sebi Cioaba Aug 7 '15 at 18:43
• @Jim I have unlocked the question, and you should be able to edit it now. – Artem Kaznatcheev Jun 4 '16 at 21:35