This is a followup question relating to an older question I posted, namely: https://cs.stackexchange.com/questions/55213/decomposing-the-n-cube-into-vertex-disjoint-paths.

Given a graph $G = (V, E)$ and sets of distinct vertices $S = \{s_1, \ldots s_k \}$ and $T = \{t_1, \ldots t_k\}$, I am interested in finding a vertex disjoint path cover $P = \{P_1, \ldots P_k\}$ of $G$ such that each $P_i$ begins with $s_i$ and ends with $t_i$. Moreover, for $P$ to be a path cover of $G$, every vertex $v \in V$ must be part of a unique path $P_i \in P$.

In my previous question, I was interested in the case when $G = \mathcal{Q}_n$ where $\mathcal{Q}_n$ denotes the $n$ dimensional hypercube graph. It was shown by Gregor and Dvorak that such a cover exists when $P$ is 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$.

Now I am interested in the same problem for a graph $G = \mathcal{Q}_n - \mathcal{Q}_d$ (i.e a single copy of $\mathcal{Q}_d$ is deleted from $\mathcal{Q}_n$), for $1 \leq d \leq n$. Results were shown for the existence of Hamiltonian cycles in graphs for graphs $\mathcal{Q}_n - G$ when $G$ is an isometric tree or cycle (http://davpe.net/download/mff/bc_revised.pdf), but nothing for the problem of path covers in the desired graph class $G = \mathcal{Q}_n - \mathcal{Q}_d$. Is anyone familiar with such results?

I am primarily interested in results for $1 \leq k \leq 2$, though I would appreciate results for any $k$.


migrated from cs.stackexchange.com May 11 '16 at 17:03

This question came from our site for students, researchers and practitioners of computer science.

Your Answer

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

Browse other questions tagged or ask your own question.