On orthogonal double covers of graphs (Q5906867): Difference between revisions

An orthogonal double cover of a graph \(G\) of order \(n\) is a collection \(\{G_1, G_2, \dots, G_n\}\) of subgraphs of \(G\) in which every edge of \(G\) is contained in exactly two subgraphs and in which every pair of subgraphs intersects in at most one edge. In a clear and interesting manner, the authors show that an orthogonal double cover of a graph \(G\) can be obtained from any permutation of the edge set of \(G\) by means of a transformation. Furthermore, they use the transformation and self-orthogonal latin squares to prove a conjecture of Chung and West: for all positive integers \(n\), there exists an orthogonal double cover of \(K_n\) in which each subgraph has maximum degree 2. The authors produce an orthogonal double cover of \(K_n\) in which each subgraph is an almost 2-factor, for all \(n \notin \{2,3,6\}\). Finally, they show that there exists an orthogonal double cover of the complete directed graph \(D_n\), for all \(n \notin \{2, 3, 6\}\).