Orthogonal double covers of complete graphs by trees (Q1376062)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Orthogonal double covers of complete graphs by trees |
scientific article |
Statements
Orthogonal double covers of complete graphs by trees (English)
0 references
24 March 1998
0 references
A collection \({\mathcal C}=\{G_1,G_2,\dots,G_n\}\) of subgraphs of the complete graph \(K_n\) is called an orthogonal double cover of \(K_n\) if every edge of \(K_n\) belongs to exactly two members of \(\mathcal C\), and any two distinct subgraphs \(G_i\) and \(G_j\) have exactly one edge in common. If each subgraph in the collection is connected, then they must be trees and this is where the authors concentrate their efforts. They find orthogonal double covers of \(K_n\) by certain families of trees and make the following intriguing conjecture: If \(T\) is an arbitrary tree with \(n\geq 2\) vertices, other than the path of order 4, then there exists an orthogonal double cover of \(K_n\) by \(T\).
0 references
orthogonal double cover
0 references
tree
0 references