Orthogonal Double Covers of Complete Graphs by Lobsters of Diameter 5

Abstract

An orthogonal double cover (ODC) of the complete graph $K_n$ by a graph $G$ is a collection $\mathcal{G}=\{G_i\mid i=1,2,\dots ,n\}$ of spanning subgraphs of $K_n$, all isomorphic to $G$, with the property that every edge of $K_n$ belongs to exactly two members of $\mathcal{G}$ and any two distinct members of $\mathcal{G}$ share exactly one edge.

A lobster of diameter five is a tree arising from a double star by attaching any number of pendant vertices to each of its vertices of degree one. We show that for any double star $R(p,q)$ there exists an ODC of $K_n$ by all lobsters of diameter five (with finitely many possible exceptions) arising from $R(p,q)$.