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 <>
Submitted on : Friday, August 14, 2015 - 2:58:33 PM
Last modification on : Thursday, May 11, 2017 - 1:02:52 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:10:28 AM


Publisher files allowed on an open archive


  • HAL Id : hal-01184431, version 1



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. ⟨hal-01184431⟩