Partitioning the vertices of a torus into isomorphic subgraphs

Journal article

Let H be an induced subgraph of the torus Ckm. We show that when k≥3 is even and |V(H)| divides some power of k, then for sufficiently large n the torus Ckn has a perfect vertex-packing with induced copies of H. On the other hand, disproving a conjecture of Gruslys, we show that when k is odd and not a prime power, then there exists H such that |V(H)| divides some power of k, but there is no n such that Ckn has a perfect vertex-packing with copies of H. We also disprove a conjecture of Gruslys, Leader and Tan by exhibiting a subgraph H of the k-dimensional hypercube Qk, such that there is no n for which Qn has a perfect edge-packing with copies of H.

Authors: Bonamy, M; Morrison, N; Scott, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Journal of Combinatorial Theory, Series A
• Volume: 174
• Article number: 105252
• Publication date: 2020-03-26
• Acceptance date: 2020-03-18
• DOI: 10.1016/j.jcta.2020.105252
• EISSN: 1096-0899
• ISSN: 0097-3165
• Language: English
• Keywords: decompositions; packings and tilings; torus