Cheap and Secure Web Hosting Provider : See Now

[Solved]: Decomposing the n-cube into vertex-disjoint paths

, , No Comments
Problem Detail: 

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.

Asked By : user340082710

Answered By : user340082710

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:

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback