2023/08/15 by Ajani De Vas Gunasekara, Alice Devillers, Gunasekara, Ajani De Vas +1
Computer Science · Engineering · Mathematics · #05C25 #05C38 #05E20 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Group Theory (math.GR) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2308.07684
openalex publication_date 2023/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Kn \Box Kn 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.