Nomadic Decompositions of Bidirected Complete Graphs

Details Nomadic Decompositions of Bidirected Complete Graphs Nomadic Decompositions of Bidirected Complete Graphs

2006-09-05

arxiv.org/abs/math/0609123v1

Discrete Math. Vol. 308, no. 17, 2008, pp. 3982-3985

Mathematics

Combinatorics

Scientific paper

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$.

Affiliated with

Also associated with

No associations

Rating

Nomadic Decompositions of Bidirected Complete Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nomadic Decompositions of Bidirected Complete Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nomadic Decompositions of Bidirected Complete Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-554954