DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Spanning paths in hypercubes

Tomáš Dvořák, Petr Gregor, Václav Koubek


Given a family {ui,vi}i=1k of pairwise distinct vertices of the n-dimensional hypercube Qn such that the distance of ui and vi is odd and k≤n-1, there exists a family {Pi}i=1k of paths such that ui and vi are the endvertices of Pi and {V(Pi)}i=1k partitions V(Qn). This holds for any n≥2 with one exception in the case when n=k+1=4. On the other hand, for any n≥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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional