281 KB22 KB200820252015Dupuis, MichaelWagon, Stanštevilka:1letnik:9str. 115-124COBISSID:17584985ISSN:1855-3966URN:URN:NBN:SI:doc-V2Z5F9ZGenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneageneralized Petersen graphsgraf skakačevih skokovHamilton-connectedHamiltonian pathsHamilton-laceableHamiltonove potihamiltonsko-povezanhamiltonsko-premostljivknight graphposplošeni Petersenovi grafisledljivtraceableLaceable knights|A bipartite graph is Hamilton-laceable if for any two vertices in different parts there is a Hamiltonian path from one to the other. Using two main ideas (an algorithm for finding Hamiltonian paths and a decomposition lemma to move from smaller cases to larger) we show that the graph of knight's moves on an ?$m \times n$? board is Hamilton-laceable iff ?$m \ge 6$?, ?$n \ge 6$?, and one of ?$m$?, ?$n$? is even. We show how the algorithm leads to new conjectures about Hamiltonian paths for various families, such as generalized Petersen graphs, ?$I$?-graphs, and cubic symmetric graphsDvodelen graf je hamiltonsko-premostljiv če za poljubni dve vozlišči iz različnih delov obstaja Hamiltonova pot od enega do drugega. Z uporabo dveh glavnih idej (algoritem za najdenje Hamiltonovih poti in dekompozicijska lema za premik od manjših primerov k večjim) pokažemo, da je graf skakačevih skokov na ?$m \times n$? šahovski deski Hamiltonsko-premostljiv če in samo če je ?$m \ge 6$?, ?$n \ge 6$?, in je eden od ?$m$?, ?$n$? sod. Pokažemo, kako algoritem vodi k novim domnevam o Hamiltonovih poteh za različne družine, kot so npr. generalizirani Petersenovi grafi, ?$I$?-grafi in kubični simetrični grafiTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije