Graph decompositions into generalized cubes

The generalized cube \(Q_{d,k}\) is the Cartesian product of \(d\) copies of \(K_k\). It is shown that if \(k\) is a prime power and \(k^{d- 1}=qd+r\), with \(0\leq r<d\), then the \(k\)-partite complete graph with partite sets of order \(k^{d-1}\), \(K_{k\times k^{d-1}}\), can be decomposed into \(q\) copies of \(Q_{d,k}\) and \(k^{d-r}\) copies of vertex-disjoint copies of \(Q_{r,k}\). Similarly it is shown that if \(k\) is a prime power and \((k^{d}-1)/(k-1)=qd+r\), with \(0\leq r<d\), then \(K_{k^{d}}\) can be decomposed into \(q\) copies of \(Q_{d,k}\) and \(k^{d-r}\) vertex-disjoint copies of \(Q_{r,k}\). Similar results for complete multigraphs and complete \(k\)-partite multigraphs are also proved. Further it is shown that \(K_{96}\) can be decomposed into 57 copies of the cube \(Q_{5}\).

Recommendations

Cited in

(9)

This page was built for publication: Graph decompositions into generalized cubes

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