Cyclic Orthogonal Double Covers of Complete Graphs by Some Complete Multipartite Graphs

Abstract

An orthogonal double cover (ODC) of the complete graph \(K_n\) is a collection \(\mathcal{G} = \{G_1,G_2,\ldots,G_n\}\) of \(n\) subgraphs of \(K_n\), such that every edge of \(K_n\) belongs to exactly two of the \(G_i\)’s and every pair of \(G_i\)’s intersect in exactly one edge. If \(G_i \cong G\) for all \(i \in \{1,2,\ldots,n\}\), then \(\mathcal{G}\) is an ODC of \(K_n\) by \(G\). An ODC of \(K_n\) is \emph{cyclic} (CODC) if the cyclic group of order \(n\) is a subgroup of its automorphism group. In this paper, we find CODCs of complete graphs by the complete multipartite graphs \(K_{2,r,s}\), \(K_{1,1,r,s}\), and \(K_{1,1,1,1,r}\).