Hamiltonian paths with prescribed edges in hypercubes |
| |
Authors: | Tomáš Dvo?ák |
| |
Institution: | Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, 11800 Praha, Czech Republic |
| |
Abstract: | Given a set P of at most 2n-4 prescribed edges (n?5) and vertices u and v whose mutual distance is odd, the n-dimensional hypercube Qn contains a hamiltonian path between u and v passing through all edges of P iff the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as endvertices. This resolves a problem of Caha and Koubek who showed that for any n?3 there exist vertices u,v and 2n-3 edges of Qn not contained in any hamiltonian path between u and v, but still satisfying the condition above. The proof of the main theorem is based on an inductive construction whose basis for n=5 was verified by a computer search. Classical results on hamiltonian edge-fault tolerance of hypercubes are obtained as a corollary. |
| |
Keywords: | 05C38 05C45 68M10 68M15 68R10 |
本文献已被 ScienceDirect 等数据库收录! |
|