Skip to Main content Skip to Navigation
Conference papers

Spanning paths in hypercubes

Abstract : 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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 2:58:33 PM
Last modification on : Wednesday, November 10, 2021 - 5:38:03 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:10:28 AM


Publisher files allowed on an open archive




Tomáš Dvořák, Petr Gregor, Václav Koubek. Spanning paths in hypercubes. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.363-368, ⟨10.46298/dmtcs.3442⟩. ⟨hal-01184431⟩



Record views


Files downloads