Affordable Access

Nomadic Decompositions of Bidirected Complete Graphs

Authors
  • Cranston, Daniel W.
Type
Published Article
Publication Date
Sep 05, 2006
Submission Date
Sep 05, 2006
Identifiers
arXiv ID: math/0609123
Source
arXiv
License
Unknown
External links

Abstract

We use $K^*_n$ to denote the bidirected complete graph on $n$ vertices. A nomadic Hamiltonian decomposition of $K^*_n$ 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$. J.A. Bondy asked whether these decompositions of $K^*_n$ exist for all $n$. We show that $K^*_n$ admits a nomadic near-Hamiltonian decomposition when $n\not\equiv 2\bmod 4$.

Report this publication

Statistics

Seen <100 times