Transitive path decompositions of Cartesian products of complete graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918519580393472 |
|---|---|
| author | Gunasekara, Ajani De Vas Devillers, Alice |
| author_facet | Gunasekara, Ajani De Vas Devillers, Alice |
| contents | An $H$-decomposition of a graph $Γ$ is a partition of its edge set into subgraphs isomorphic to $H$. A transitive decomposition is a special kind of $H$-decomposition that is highly symmetrical in the sense that the subgraphs (copies of $H$) are preserved and transitively permuted by a group of automorphisms of $Γ$. This paper concerns transitive $H$-decompositions of the graph $K_n \Box K_n$ where $H$ is a path. When $n$ is an odd prime, we present a construction for a transitive path decomposition where the paths in the decomposition are considerably large compared to the number of vertices. Our main result supports well-known Gallai's conjecture and an extended version of Ringel's conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_07684 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Transitive path decompositions of Cartesian products of complete graphs Gunasekara, Ajani De Vas Devillers, Alice Combinatorics Group Theory 05C38, 05E20, 05C25 An $H$-decomposition of a graph $Γ$ is a partition of its edge set into subgraphs isomorphic to $H$. A transitive decomposition is a special kind of $H$-decomposition that is highly symmetrical in the sense that the subgraphs (copies of $H$) are preserved and transitively permuted by a group of automorphisms of $Γ$. This paper concerns transitive $H$-decompositions of the graph $K_n \Box K_n$ where $H$ is a path. When $n$ is an odd prime, we present a construction for a transitive path decomposition where the paths in the decomposition are considerably large compared to the number of vertices. Our main result supports well-known Gallai's conjecture and an extended version of Ringel's conjecture. |
| title | Transitive path decompositions of Cartesian products of complete graphs |
| topic | Combinatorics Group Theory 05C38, 05E20, 05C25 |
| url | https://arxiv.org/abs/2308.07684 |