Decompositions and Packings of Digraphs with Orientations of a \(4\)-Cycle

Robert B.Gardner1, Coleen Huff2, Janie Kennedy3
1Institute of Mathematical and Physical Sciences East Tennessee State University Johnson City, Tennessee 37614 — 0663
2Department of Mathematics East Tennessee State University in Kingsport Kingsport, Tennessee 37660
3Department of Mathematics and Computer Science Samford University Birmingham, AL 35229

Abstract

We present necessary and sufficient conditions for the decomposition of the complete symmetric bipartite digraph into each of the orientations of a \(4\)-cycle (in the cases for which such decompositions are not already known). We use these results to find optimal packings of the complete symmetric digraph with each of the orientations of a \(4\)-cycle. Finally, we give necessary and sufficient conditions for the existence of a decomposition of the complete symmetric digraph on \(v\) vertices with a hole of size \(w\) into each of the orientations of a \(4\)-cycle.