# Decomposition of a regular graph and connected subgraphs

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.

• The comments on my answer lead me to wonder: is the condition on the successive decompositions supposed to hold for every possible choice of the $x_i$, or just for one? Jul 28, 2015 at 16:48
• @KlausDraeger I guess , since all graphs stated in the problem are regular graphs( which is practically not possible though but this post is needed in a certain situation), every vertex is same with respect to the process used in this problem . Jul 28, 2015 at 16:55
• That would be true if you required your graph to be transitive, but I don't see how mere regularity gets you there. Jul 28, 2015 at 17:06
• @KlausDraeger , because main issue here is empty or non empty edge set between $C_2,D_2$, not the "nature or structure " of connections/ edges, like graph isomorphism testing needs. you said "is the condition on the successive decompositions supposed to hold for every possible choice of the $x_i$, or just for one?" are u considering the recursive function asked in earlier question(linked to this post)? Jul 28, 2015 at 17:40

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.

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.

• I think answer is negative, more generally , it is impossible to have no edge when $t_2$ and $s_2 >0$ . See my answer, mathoverflow.net/questions/211894/… Jul 28, 2015 at 15:51
• but every sub graph obtained by this procedure, is complete graph( considering bipartite complete graph), edge set between $C,D$ always will be either empty or full, right? Jul 28, 2015 at 21:48
• Yes, that is right. Jul 29, 2015 at 0:57