Partitioning the vertices of a torus into isomorphic subgraphs

Author: 

Bonamy, M
Morrison, N
Scott, A

Publication Date: 

1 August 2020

Journal: 

JOURNAL OF COMBINATORIAL THEORY SERIES A

Last Updated: 

2020-10-31T08:54:59.353+00:00

Volume: 

174

DOI: 

10.1016/j.jcta.2020.105252

abstract: 

© 2020 Elsevier Inc. 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.

Symplectic id: 

1099399

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article