Tomáš Dvořák ; Petr Gregor ; Václav Koubek
-
Spanning paths in hypercubes
dmtcs:3442 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3442
Spanning paths in hypercubesArticle
Authors: Tomáš Dvořák 1; Petr Gregor 1; Václav Koubek 2
NULL##NULL##NULL
Tomáš Dvořák;Petr Gregor;Václav Koubek
1 Faculty of Mathematics and Physics [Praha/Prague]
2 Institute for Theoretical Computer Science
Given a family $\{u_i,v_i\}_{i=1}^k$ of pairwise distinct vertices of the $n$-dimensional hypercube $Q_n$ such that the distance of $u_i$ and $v_i$ is odd and $k \leq n-1$, there exists a family $\{P_i\}_{i=1}^k$ of paths such that $u_i$ and $v_i$ are the endvertices of $P_i$ and $\{V(P_i)\}_{i=1}^k$ partitions $V(Q_n)$. This holds for any $n \geq 2$ with one exception in the case when $n=k+1=4$. On the other hand, for any $n \geq 3$ there exist $n$ pairs of vertices satisfying the above condition for which such a family of spanning paths does not exist. We suggest further generalization of this result and explore a relationship to the problem of hamiltonicity of hypercubes with faulty vertices.
S. A. Choudum;S. Lavanya;V. Sunitha, 2010, Disjoint paths in hypercubes with prescribed origins and lengths, International Journal of Computer Mathematics, 87, 8, pp. 1692-1708, 10.1080/00207160802566805.