Ramadan El-Shanawany, Hans-Dietrich O.F. Gronau, Martin Grüttmüller
Orthogonal Double Covers of $\mathbf{K_{n,n}}$ by Small Graphs
Preprint series: Preprints aus dem Fachbereich Mathematik, Universität Rostock

MSC:

05C70 Factorization, matching, covering and packing

05B40 Packing and covering, See also {11H31, 52C15, 52C17}

Abstract: An orthogonal double cover (ODC) of $K_n$ is a collection of
graphs such that each edge of $K_n$ occurs in exactly two of the
graphs and two graphs have precisely one edge in common.
ODCs of $K_n$ and their generalizations have been extensively
studied by several authors (e.g. \cite{ahl92,gmr97,le00}).
In this paper, we investigate ODCs where the graph to be
covered twice is $K_{n,n}$ and all graphs in the collection
are isomorphic to a given small graph $G$.
We prove that there exists an ODC of $K_{n,n}$ by all proper
subgraphs $G$ of $K_{n,n}$ for $1 \leq n \leq 9$, with two
genuine exceptions.
Keywords: orthogonal double cover, ODC, graph decompositions