0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Klaus Draeger Jul 28 '15 at 16:48
  • $\begingroup$ @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 . $\endgroup$ – Jim Jul 28 '15 at 16:55
  • $\begingroup$ That would be true if you required your graph to be transitive, but I don't see how mere regularity gets you there. $\endgroup$ – Klaus Draeger Jul 28 '15 at 17:06
  • $\begingroup$ @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)? $\endgroup$ – Jim Jul 28 '15 at 17:40
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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/… $\endgroup$ – Jim Jul 28 '15 at 15:51
  • $\begingroup$ 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? $\endgroup$ – Jim Jul 28 '15 at 21:48
  • $\begingroup$ Yes, that is right. $\endgroup$ – Klaus Draeger Jul 29 '15 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.