Transitive path decompositions of Cartesian products of complete graphs

Authors

Ajani De Vas Gunasekara, The University of Notre Dame Australia

Publication Details

De Vas Gunasekara, A. (2024). Transitive path decompositions of Cartesian products of complete graphs. Designs, Codes and Cryptography,.

Abstract

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_nK_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.

Keywords

path decompositions, transitive decompositions, Cartesian products of graphs, group actions on graphs

Link to Publisher Version (URL)

10.1007/s10623-024-01493-9