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

  • $\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$ – Joonas Ilmavirta Nov 27 '14 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 '14 at 9:55

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.

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

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.