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 hypercubes
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.
CastaĂąeda, Nelson; Gotchev, Ivan S., 2014, Path Coverings With Prescribed Ends In Faulty Hypercubes, Graphs And Combinatorics, 31, 4, pp. 833-869, 10.1007/s00373-014-1426-0.
Choudum, S. A.; Lavanya, S.; Sunitha, V., 2010, Disjoint Paths In Hypercubes With Prescribed Origins And Lengths, International Journal Of Computer Mathematics, 87, 8, pp. 1692-1708, 10.1080/00207160802566805.