5
$\begingroup$

I am not sure if this question is better suited for cs.stackexchange or math.stackexchange - This is of interested to me in the context of a data structure problem, but the question itself may be better suited elsewhere. If so, please feel free to move my question.

Let $\mathcal{Q}_n$ denote the $n$-cube graph. Given a set of vertices $S = \{s_1, \ldots s_k \}$ and $T = \{t_1, \ldots t_k\}$, we would like to decompose $\mathcal{Q}_n$ into $k$ vertex disjoint paths $P_1, \ldots P_k$, such that each $P_i$ begins with $s_i$ and ends with $t_i$. Here, two paths are vertex-disjoint if they do not share any vertices. In addition, I require that every vertex in $\mathcal{Q}_n$ be part of some path $P_j$. I would like to know under what conditions (particularly on $S$ and $T$) can we guarantee that such a decomposition exists?

Also, I would like to know the name of this problem so that I can better search for references.

$\endgroup$
5
$\begingroup$

I found the following result due to Gregor and Dvorak. They show that if the sets $S$ and $T$ are balanced (in the sense that they contain the same amount of vertices from both bi-partitions of the $n$-cube), then such paths exists whenever $2k-e < n$, where $e$ is the number of pairs $(s_i, t_i)$ that form edges in $\mathcal{Q}_n$. The paper can be found here: http://www.sciencedirect.com/science/article/pii/S0020019008002238

I can construct an example when $k = 2$, $e=0$ and $n=3$, so this result isn't completely tight, however.

$\endgroup$

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.