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
    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
    0 references
    0 references
    0 references
    0 references
    orthogonal double cover
    0 references
    tree
    0 references
    0 references
    0 references
    0 references