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

https://hal.inria.fr/hal-01184431
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

File

dmAE0170.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

100

Files downloads

634