Partitioning the vertices of a torus into isomorphic subgraphs
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...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2020
|
| _version_ | 1826290612126613504 |
|---|---|
| author | Bonamy, M Morrison, N Scott, A |
| author_facet | Bonamy, M Morrison, N Scott, A |
| author_sort | Bonamy, M |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T02:46:51Z |
| format | Journal article |
| id | oxford-uuid:ac54b5d3-4b6f-4ddc-bb6f-8016bccd3a9b |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T02:46:51Z |
| publishDate | 2020 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:ac54b5d3-4b6f-4ddc-bb6f-8016bccd3a9b2022-03-27T03:28:15ZPartitioning the vertices of a torus into isomorphic subgraphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:ac54b5d3-4b6f-4ddc-bb6f-8016bccd3a9bEnglishSymplectic ElementsElsevier 2020Bonamy, MMorrison, NScott, ALet 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. |
| spellingShingle | Bonamy, M Morrison, N Scott, A Partitioning the vertices of a torus into isomorphic subgraphs |
| title | Partitioning the vertices of a torus into isomorphic subgraphs |
| title_full | Partitioning the vertices of a torus into isomorphic subgraphs |
| title_fullStr | Partitioning the vertices of a torus into isomorphic subgraphs |
| title_full_unstemmed | Partitioning the vertices of a torus into isomorphic subgraphs |
| title_short | Partitioning the vertices of a torus into isomorphic subgraphs |
| title_sort | partitioning the vertices of a torus into isomorphic subgraphs |
| work_keys_str_mv | AT bonamym partitioningtheverticesofatorusintoisomorphicsubgraphs AT morrisonn partitioningtheverticesofatorusintoisomorphicsubgraphs AT scotta partitioningtheverticesofatorusintoisomorphicsubgraphs |