Complete bipartite factorisations by complete bipartite graphs

DOI10.1016/S0012-365X(97)00248-3MaRDI QIDQ1356485zbMATH OpenOpenAlexFDO

Publication date 5 January 1998

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(97)00248-3

complete bipartite graph factorization tessellations of the plane

Combinatorial aspects of tessellation and tiling problems (05B45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

Let \(K_{m,n}\) be the complete bipartite graph on sets of size \(m\) and \(n\). A \(K_{p,q}\)-factor of \(K_{m,n}\) is a spanning subgraph of \(K_{m,n}\) which is a union of vertex-disjoint subgraphs each isomorphic to \(K_{p,q}\). If \(K_{m,n}\) is expressed as a edge-disjoint union of \(K_{p,q}\)-factors, then this union is called a \(K_{p,q}\)-factorization of \(K_{m,n}\). Several basic arithmetic conditions are derived which must be satisfied if there exists such a factorization. The author conjectures that these conditions are also sufficient for the existence of a factorization. Tessellations of the plane by rectangles are used to prove the conjecture in many cases. In particular, the conjecture is proved for \(K_{1,q}\)-factorizations of \(K_{n,n}\) except for \(q= 4k+1\) and for a certain family of \(K_{1,3}\)-factorizations.

Recommendations

Cites work

Cited in

(24)

This page was built for publication: Complete bipartite factorisations by complete bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356485)