1. Spanning paths in hypercubes
- Author
-
Tomáš Dvořák, Petr Gregor, and Václav Koubek
- Subjects
hamiltonian paths ,spanning paths ,hypercube ,vertex fault tolerance ,[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] ,[math.math-co] mathematics [math]/combinatorics [math.co] ,Mathematics ,QA1-939 - 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.
- Published
- 2005
- Full Text
- View/download PDF