Nomadic decompositions of bidirected complete graphs |
| |
Authors: | Daniel W. Cranston |
| |
Affiliation: | University of Illinois, Urbana-Champaign, Illinois, USA |
| |
Abstract: | We use to denote the bidirected complete graph on n vertices. A nomadic Hamiltonian decomposition of is a Hamiltonian decomposition, with the additional property that “nomads” walk along the Hamiltonian cycles (moving one vertex per time step) without colliding. A nomadic near-Hamiltonian decomposition is defined similarly, except that the cycles in the decomposition have length n-1, rather than length n. Bondy asked whether these decompositions of exist for all n. We show that admits a nomadic near-Hamiltonian decomposition when . |
| |
Keywords: | Hamiltonian Decomposition Nomad |
本文献已被 ScienceDirect 等数据库收录! |
|