Orthogonally Resolvable Cycle Decompositions

If a cycle decomposition of a graph G admits two resolutions, R and S , such that| R i ∩ S j | ≤ 1for each resolution classR i ∈ R andS j ∈ S , then the resolutions R and S are said to be orthogonal . In this paper, we introduce the notion of an orthogonally resolvable cycle decomposition, which is a cycle decomposition admitting a pair of orthogonal resolutions. An orthogonally resolvable cycle decomposition of a graph G may be represented by a square array in which each cell is either empty or filled with a k –cycle from G , such that every vertex appears exactly once in each row and column of the array and every edge of G appears in exactly one cycle. We focus mainly on orthogonal k ‐cycle decompositions of K n andK n − I (the complete graph with the edges of a 1‐factor removed), denotedOCD ( n , k ) . We give general constructions for such decompositions, which we use to construct several infinite families. We find necessary and sufficient conditions for the existence of an OCD( n , 4). In addition, we consider orthogonal cycle decompositions of the lexicographic product of a complete graph or cycle withK n ¯ . Finally, we give some nonexistence results.