Factorizations of \(K_{m,n}\) into spanning trees (Q1808713)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Factorizations of \(K_{m,n}\) into spanning trees
scientific article

    Statements

    Factorizations of \(K_{m,n}\) into spanning trees (English)
    0 references
    0 references
    0 references
    0 references
    25 November 1999
    0 references
    Let \(G\) be a graph. A sequence \(H_1,\dots, H_n\) is called a decomposition of \(G\) if each edge of \(G\) is in exactly one \(H_i\). A spanning subgraph \(F\) of \(G\) is called a factor of \(G\). If in addition each component of \(F\) is isomorphic to a graph \(H\), \(F\) is called an \(H\)-factor of \(G\). A decomposition of \(G\) into \(H\)-factors is called an \(H\)-factorization of \(G\). The paper shows that there is a spanning tree factorization of \(K_{n,m}\) if \(m+n-1\) divides \(mn\). Moreover, the factorization with isomorphic spanning trees is discussed.
    0 references
    0 references
    decomposition
    0 references
    factor
    0 references
    spanning tree
    0 references
    factorization
    0 references
    0 references
    0 references