Sven Hartmann, Ulrike Schumacher
Suborthogonal double covers of complete graphs
Preprint series: Preprints aus dem Fachbereich Mathematik, Universitt Rostock

MSC:

05C70 Factorization, matching, covering and packing

05B30 Other designs, configurations, See also {51E30}

Abstract: A family $\mathcal{G}$ of isomorphic copies of a given graph $G$ is
said to be a suborthogonal double cover (SODC) of the complete graph
$K_n$ by $G$, if every edge of $K_n$ belongs to exactly two members
of $\mathcal{G}$ and any two different elements from $\mathcal{G}$
share at most one edge. We introduce the notion of an SODC as a
generalization of the well-known concept of orthogonal double covers.
Our objective is to investigate the sets $S(G)$ of integers $n$
allowing an SODC of $K_n$ by a given graph $G$. We shall prove that
$S(G)$ contains almost all integers $n$ satisfying certain necessary
conditions.
Keywords: decomposition, cover, suborthogonal, graph