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
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
decomposition
0 references
factor
0 references
spanning tree
0 references
factorization
0 references