1
$\begingroup$

Given $n\geq 2$, let us consider the n-cube $H_n=(V,E)$, i.e. vertex set $V$ is $\{0,1\}^n$. Here, the edges of $H_n$ are directed, oriented by set inclusion, i.e., $(x,y)\in E$ iff $x\subseteq y$ and $\text{dist}_{Hamm}(x,y)=1$). Let $0^n := (0, 0, \ldots, 0)$ and $1^n := (1, 1, \ldots, 1)$. Let $S\subseteq V\setminus \{0^n, 1^n\}$ such that $|S|=n$. Assume that in $H_n\setminus S$ there is no directed path from $0^n$ to $1^n$. Then, is it true that $H_n\setminus S$, now viewed as undirected graph, is disconnected (i.e. "no directed path" implies "no undirected path" in this setting) ?

$\endgroup$
2
  • $\begingroup$ What is the orientation of the edges, even for $H_3$? The $n-1$ dimensional faces of $H_n$ inherit an orientation from $H_n$, but already the $n-2$ dimensional edges inherit opposite orientations from the two adjacent $n-1$ dimensional faces. Also, do you want to assume $0^n,1^n\notin S$? $\endgroup$ Nov 27, 2014 at 9:49
  • $\begingroup$ the orientation is by set inclusion: (x,y)\in E iff x\subset y and hamming_dist(x,y)=1. And yes $0^n,1^n$ are not in $S$. Thank you. $\endgroup$
    – Xorwell
    Nov 27, 2014 at 9:55

1 Answer 1

3
$\begingroup$

Every vertex removed from the $k$th layer prohibits $k!(n-k)!\leq (n-1)!$ paths. Thus, if $n$ removed verices prohibit all $n!$ paths, then each of them prohibits exactly $(n-1)!$ paths, and the sets of prohibited paths are disjoint. This means that either all the vertices are on the first layer, or all the vertices are on the $(n-1)$th layer. In both cases their removal disconnects the unoriented graph as well.

$\endgroup$
1
  • $\begingroup$ I think so, thanks for confirming Ilya. $\endgroup$
    – Xorwell
    Nov 27, 2014 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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