490 KB22 KB98 KB2 KB2026Eppstein, Davidletnik:26številka:4, article p4.02str. 1-9DOI:10.26493/1855-3974.3557.f2dISSN:1855-3974COBISSID_HOST:294150915URN:URN:NBN:SI:doc-MZVGZQGHenUniverza na PrimorskemArs mathematica contemporanea4-valentni grafHamiltonian cycleHamiltonian decompositionHamiltonov cikelHamiltonova dekompozicijasubdivided doublesubdividirani dvojniktetravalent graphHamiltonian cycles in subdivided doubles|The subdivided double construction on 4-regular graphs was used by Potočnik and Wilson to explore semi-symmetric graphs. It preserves the property of being semi-symmetric, and can be used to construct every semi-symmetric 4-regular graph that contains a pair of twin vertices. We show that (regardless of symmetry) subdivided doubles have another curious property: each of their many Hamiltonian cycles is complementary to another Hamiltonian cycleKonstrukcijo subdividiranega dvojnika na 4-regularnih grafih sta Potočnik in Wilson uporabila pri raziskovanju polsimetričnih grafov (povezavno tranzitivnih, vendar ne vozliščno tranzitivnih grafov), z njo pa je mogoče konstruirati vsak polsimetričen 4-regularen graf, ki vsebuje par dvojnih vozlišč. Pokažemo, da imajo subdividirani dvojniki, ne glede na simetrijo, še eno zanimivo lastnost: imajo eksponentno mnogo Hamiltonovih ciklov, pri čemer je vsak izmed njih komplementaren nekemu drugemu Hamiltonovemu cikluTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije