Decomposition of a regular graph and connected subgraphs

Question

I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in my approach, I will not use matrix and recursive process, instead, this time I describe the problem for first two consecutive steps. Despite my effort, if it is not clear, please, let me know.

Problem Description: $G$ is a $r$ regular graph. $G$ is $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 $. These $C_1, D_1 $ are $s_1 , t_1 $ regular graphs respectively (given condition) . 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 $. These $C_2, D_2 $ are $s_2 , t_2 $ regular graphs respectively(given condition).

Question: According to above given conditions/situation/context, is it possible to have no edge between graph $C_2$ and $ D_2 $?

Motivation: I am studying graph isomorphism problem. In a certain kind of construction, above described situation arises and increases search cases. I am trying to find out when this (no edge between sub-graphs $C_y, D_y$ ) can happen. I hope, this post is an appropriate MO question.

Answer 1

Edit: How about this counterexample for the case $s_2,t_2>0$:

$G=(V,E)$ with $V=\{x_1\}\cup\{u_i^k\ |\ 1\le i\le n,1\le k\le 4\}$, and $E$ being the union of

• $\{(x_1,u_i^k)\ |\ 1\le i\le n, k\in\{1,4\}\}$,
• $\{(u_i^k,u_j^k)\ |\ 1\le i<j\le n, k\in\{1,4\}\}$,
• $\{(u_i^k,u_j^{k+1})\ |\ 1\le i,j\le n, 1\le k\le 3\}$.

$G$ is $2n$-regular. Decomposing with respect to $x_1$, we get that $C_1$ is the complete bipartite graph on $\{u_i^2\ |\ 1\le i\le n\}$ and $\{u_i^3\ |\ 1\le i\le n\}$ (and thus $n$-regular), while $D_1$ is the disjoint union of the complete graphs on $\{u_i^1\ |\ 1\le i\le n\}$ and $\{u_i^4\ |\ 1\le i\le n\}$ (and thus $(n-1)$-regular).

Picking (for example) $x_2=u_1^1$, we now get that $C_2$ is the complete graph on $\{u_i^4\ |\ 1\le i\le n\}$, and $D_2$ is the complete graph on $\{u_i^1\ |\ 2\le i\le n\}$. There are no edges between these, and they are $(n-1)$- and $(n-2)$-regular, respectively.

Old, simpler answer:

I will assume that you meant $x_i$ to not be included in $C_i$ (otherwise you would need to go for an example where $D_2$ is the null graph).

For $k\in\mathbb{N}$, consider the graph $G = (\{u_1,\dots,u_{2k},v_1,\dots,v_{2k-1}\},E)$, where $E$ contains the following edges:

• $(u_{2i-1},u_{2i})$ for $i=1,\dots,k$;
• $(u_i,v_j)$ for all $i,j$.

$G$ is $2k$-regular. Picking $x_1=v_1$, $C_1$ is $(\{v_i\ |\ i>1\},\emptyset)$ ($0$-regular), and $D_1$ is $(\{u_1,\dots,u_{2n}\},\{(u_{2i-1},u_{2i})\ |\ 1\le i\le k\})$ ($1$-regular).

Picking $x_2=u_1$, we get $C_2=(\{u_i\ |\ i>2\},\{(u_{2i-1},u_{2i})\ |\ 1<i\le k\})$ ($1$-regular) and $D_2=(\{u_2\},\emptyset)$ ($0$-regular), with no edges between them.