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,\dots ,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,\dots ,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}$.