On oriented path double covers (Q5936044)

Denote by \(G_S\) the symmetric orientation of \(G\) (e.g. \(V(G_S)=V(G)\) and \(E(G_S)=\{(u,v),(v,u)\mid \{u,v\}\in E(G)\}).\) An oriented perfect path double cover (OPPDC) of a graph \(G\) is a collection of paths in \(G\) such that each edge of \(G_S\) lies in exactly one of the paths and each vertex of \(G\) appears just once as a beginning and just once as an end of a path. The authors consider OPPDC for complete graphs. They prove that \(K_3\) and \(K_5\) have no OPPDC while all \(K_{2n}\) admit an OPPDC. Using computers they have also found an OPPDC for \(K_{2n+1}\) for small \(n\). The authors discuss the structure of the minimal (i.e., with minimal number of edges) connected graphs \(G\) such that \(G\not= K_3\), \(G\not= K_5\) and \(G\) has no OPPDC. They show that \(G\) has no vertices of degree 1, 2 or 3. As a consequence of this it is shown that a union of two arbitrary trees has an OPPDC and that all 2-connected graphs on \(n\) vertices with at most \(2n-1\) edges have an OPPDC (except for \(K_3\)).