<p><strong>Motivation:</strong> I am studying the graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases .</p>

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

<p>Using same method, based on adjacency of $x_2$ , $D_1$ can be divided. </p>

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

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

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

<ol>
<li><p>$C_y,  D_y $  are $s_y , t_y&gt;0 $ regular graphs respectively for all iteration $y$</p></li>
<li><p>$C_y,  D_y $  cannot be complete bipartite graph (utility graph), complete graph or disjoint union of complete graphs.</p></li>
</ol>

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

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

<p><strong>Matrix representation :</strong> 
 $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|&gt;|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 &amp; E_1  \\
E_1^{T} &amp; D_1 \\
\end{array} \right) 
$$</p>

<p>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 &amp; E_y  \\
E_y^{T} &amp; D_{y} \\
\end{array} \right) 
$$</p>

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

<p><strong>Claim:</strong><br>
 <em>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.</em></p>

<p><strong>Question: how  a graph can be constructed  so that the graph has regular subgraph as described above?</strong> </p>

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

CC BY-SA 3.0
2015-07-31T23:24:30.040Z
@Brendan can you cite something that would point to "the hardest graphs for the isomorphism problem"? arent they thought to be regular? thx!
vzn
CC BY-SA 3.0
2015-08-01T02:08:25.360Z
@BrendanMcKay , Sir, you said , that such graphs are not the hardest graphs for the isomorphism problem, can their isomorphism be determined less than quasipolynomial time?
Michael
CC BY-SA 3.0
2016-06-04T21:35:16.463Z
@Jim I have unlocked the question, and you should be able to edit it now.
Artem Kaznatcheev
<graph-theory><ds.algorithms>
Partitioning graph for Graph Isomorphism
Michael
# Partitioning graph for Graph Isomorphism

(Asked by: username_0 on 2015-07-29)

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

**Tags:** graph-theory, ds.algorithms
> **Comments:**
> **username_1**: @Brendan can you cite something that would point to "the hardest graphs for the isomorphism problem"? arent they thought to be regular? thx!  
> **username_0**: @BrendanMcKay , Sir, you said , that such graphs are not the hardest graphs for the isomorphism problem, can their isomorphism be determined less than quasipolynomial time?  
> **username_2**: @Jim I have unlocked the question, and you should be able to edit it now.  

---

## 0 answers

