2
$\begingroup$

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

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

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

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

$\endgroup$

closed as off-topic by Todd Trimble Aug 31 '15 at 17:41

  • This question does not appear to be about research level mathematics within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ 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. $\endgroup$ – Brendan McKay Jul 29 '15 at 2:52
  • $\begingroup$ @BrendanMcKay , Sir, I was/am planing to generalize this class later.For example, Without restriction 2, there will be complete $C_y, D_y$ graphs, complete graphs are not hardest for GI, I guess. $\endgroup$ – Jim Jul 29 '15 at 9:01
  • 3
    $\begingroup$ @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. $\endgroup$ – Brendan McKay Aug 1 '15 at 2:05
  • 2
    $\begingroup$ @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/… $\endgroup$ – Brendan McKay Aug 1 '15 at 3:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Sebi Cioaba Aug 7 '15 at 18:43