On orthogonal double covers of graphs (Q5906867): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1023/a:1008283627078 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1508022909 / rank | |||
Normal rank |
Latest revision as of 11:49, 30 July 2024
scientific article; zbMATH DE number 1115727
Language | Label | Description | Also known as |
---|---|---|---|
English | On orthogonal double covers of graphs |
scientific article; zbMATH DE number 1115727 |
Statements
On orthogonal double covers of graphs (English)
0 references
28 April 1998
0 references
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\}\).
0 references
orthogonal double cover
0 references
graph decomposition
0 references