Transitive path decompositions of Cartesian products of complete graphs

Autor:	Gunasekara, Ajani De Vas, Devillers, Alice
Rok vydání:	2023
Předmět:	Mathematics - Combinatorics Mathematics - Group Theory 05C38 05E20 05C25
Druh dokumentu:	Working Paper
Popis:	An $H$-decomposition of a graph $\Gamma$ 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 $\Gamma$. 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. Comment: 15 pages, 4 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2308.07684 Zobrazit plný text záznamu View this record from Arxiv