538 KB70 KB131 KB3 KB200820262026Lacaze-Masmonteil, Aliceštevilka:2, article p2.04letnik:26str. 1-26DOI:10.26493/1855-3974.3471.51fISSN:1855-3974COBISSID_HOST:289257731URN:URN:NBN:SI:doc-H78TRFKYenUniverza na PrimorskemArs mathematica contemporaneadecompositionsdekompozicijadirected graphshamiltonian cyclehamiltonski cikelusmerjeni grafvenčni produktwreath productDecompositions of the wreath product of certain directed graphs into directed hamiltonian cycles|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 decomposablePotrdimo več posebnih primerov domneve, ki se je prvič pojavila pri Alspachu et al. (1987) in določa, da je venčni (leksikografski) produkt dveh usmerjenih grafov, ki sta razčlenljiva na hamiltonske cikle, prav tako razčlenljiv na hamiltonske cikle. Natančneje, pokažemo, da je venčni produkt hamiltonsko razčlenljivega usmerjenega grafa G, za katerega velja, da je |V (G)| sodo in |V (G)| ? 4, z usmerjenim m-ciklom, kjer je m ? 4, ali s popolnim simetričnim usmerjenim grafom na m vozliščih, kjer je m ? 3, hamiltonsko razčlenljiv. Pokažemo tudi, da venčni produkt usmerjenega n-cikla, kjer je n sodo, z usmerjenim m-ciklom, kjer je m ? {2, 3}, ni hamiltonsko razčlenljivTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije