On the Decomposition of Cayley Color Graphs into Isomorphic Oriented Trees

Abstract

We prove that if [Delta] is a minimal generating set for a nontrivial group [Gamma] and T is an oriented tree having |[Delta]| edges, then the Cayley color graph D[Delta]([Gamma]) can be decomposed into Absolute value of |[Gamma]| edge-disjoint subgraphs, each of which is isomorphic to T; we say that D[Delta]([Gamma]) is T-decomposable. This result is extended to obtain a result concerning H-decompositions of Cayley graphs for weakly connected oriented graphs H. The first result is then used to derive several theorems concerning decompositions of Cayley color graphs into prescribed families of oriented trees. Applications of some of these theorems to the verification of statements about decompositions of the n-dimensional hypercube Qn are also discussed.