Sven Hartmann, Ulrike Schumacher
Orthogonal double covers of general 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: Let H be a graph on n vertices and G a collection of
n subgraphs of H, one for each vertex.
G is an orthogonal double cover (ODC) of H
if every edge of H occurs in exactly two members of G
and any two members share an edge whenever the
corresponding vertices are adjacent in H.

ODCs of complete graphs have been widely studied in literature.
In this paper, we are concerned with ODCs of arbitrary graphs.
In particular, we investigate the existence of ODCs whose
members are isomorphic sets of independent edges.

Keywords: edge decomposition; ODC; regular graph; matching; hypercube