Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651286 | Discrete Mathematics | 2006 | 19 Pages |
Abstract
Call a directed graph G↔ symmetric if it is obtained from an undirected graph GG by replacing each edge of GG by two directed edges, one in each direction. We will show that if GG has a Hamilton decomposition with certain additional structure, then G↔×C↔n×K↔2 has a directed Hamilton decomposition. In particular, it will follow that the bidirected cubes Q↔2m+1 for m⩾2m⩾2 are decomposable into 2m+12m+1 directed Hamilton cycles and that a product of cycles C↔n1×⋯×C↔nm×K↔2 is decomposable into 2m+12m+1 directed Hamilton cycles if ni⩾3ni⩾3 and m⩾2m⩾2.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Richard Stong,