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$.


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.