Article ID Journal Published Year Pages File Type
9512619 Discrete Mathematics 2005 61 Pages PDF
Abstract
If X is any connected Cayley graph on any finite abelian group, we determine precisely which flows on X can be written as a sum of hamiltonian cycles. (This answers a question of B. Alspach.) In particular, if the degree of X is at least 5, and X has an even number of vertices, then the flows that can be so written are precisely the even flows, that is, the flows f, such that ∑α∈E(X)f(α) is divisible by 2. On the other hand, there are examples of degree 4 in which not all even flows can be written as a sum of hamiltonian cycles. Analogous results were already known, from work of B. Alspach, S.C. Locke, and D. Witte, for the case where X is cubic, or has an odd number of vertices.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,