1.
Decompositions of the wreath product of certain directed graphs into directed hamiltonian cyclesAlice Lacaze-Masmonteil, 2026, original scientific article
Abstract: We affirm several special cases of a conjecture that first appears in Alspach et al. (1987) which stipulates that the wreath (lexicographic) product of two hamiltonian decomposable di- rected graphs is also hamiltonian decomposable. Specifically, we show that the wreath product of hamiltonian decomposable directed graph G, such that |V (G)| is even and |V (G)| ⩾ 3, with a directed m-cycle such that m ⩾ 4 or the complete symmetric directed graph on m vertices such that m ⩾ 3, is hamiltonian decomposable. We also show the wreath product of a directed n-cycle, where n is even, with a directed m-cycle, where m ∈ {2, 3}, is not hamiltonian decomposable.
Keywords: wreath product, decompositions, hamiltonian cycle, directed graphs
Published in RUP: 17.03.2026; Views: 549; Downloads: 37
Full text (538,63 KB)
