On orthogonal double covers of graphs

DOI10.1023/A:1008283627078MaRDI QIDQ5906867zbMATH OpenOpenAlexFDO

Publication date 28 April 1998

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1008283627078

graph decomposition orthogonal double cover

Orthogonal arrays, Latin squares, Room squares (05B15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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\}\).

Recommendations

Cited in

(18)

This page was built for publication: On orthogonal double covers of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5906867)