692 KB52 KB200820252017Goedgebeur, JanZamfirescu, Carol T.letnik:13številka:2str. 235-257COBISSID:18354521ISSN:1855-3966URN:URN:NBN:SI:doc-PKP5T2IZenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneahamiltonski grafiteorija grafovImproved bounds for hypohamiltonian graphs|A graph ?$G$? is hypohamiltonian if ?$G$? is non-hamiltonian and ?$G - v$? is hamiltonian for every ?$v \in V(G$)?. In the following, every graph is assumed to be hypohamiltonian. Aldred, Wormald, and McKay gave a list of all graphs of order at most 17. In this article, we present an algorithm to generate all graphs of a given order and apply it to prove that there exist exactly 14 graphs of order 18 and 34 graphs of order 19. We also extend their results in the cubic case. Furthermore, we show that (i) the smallest graph of girth 6 has order 25, (ii) the smallest planar graph has order at least 23, (iii) the smallest cubic planar graph has order at least 54, and (iv) the smallest cubic planar graph of girth 5 with non-trivial automorphism group has order 78Graf ?$G$? je hipohamiltonski če in samo če je ?$G$? nehamiltonski in je ?$G - v$? hamiltonski za vsak ?$v \in V(G)$?. V nadaljnjem za vsak graf privzamemo, da je hipohamiltonski. Aldred, Wormald in McKay so podali seznam vseh grafov reda največ 17. V članku predstavimo algoritem za generiranje vseh grafov danega reda in ga uporabimo za dokaz, da obstaja natanko 14 grafov reda 18 in 34 grafov reda 19. Razširimo tudi njihove rezultate v kubičnem primeru. Nadalje pokažemo, da velja: (i) najmanjši graf ožine 6 ima red 25, (ii) najmanjši ravninski graf ima red najmanj 23, (iii) najmanjši kubični ravninski graf ima red najmanj 54, in (iv) najmanjši kubični ravninski graf ožine 5 z netrivialno grupo avtomorfizmov ima red 78TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije