Graf ?$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 78.

Pravice

URN

URN:NBN:SI:DOC-PKP5T2IZ

COBISSID

18354521

Objavljeno

29.05.2020

Metapodatki

Citiranje

APA:

Goedgebeur, Jan, Zamfirescu, Carol T. (2017). Improved bounds for hypohamiltonian graphs. Ars mathematica contemporanea, letnik 13, številka 2, str. 235-257. URN:NBN:SI:DOC-PKP5T2IZ from http://www.dlib.si

MLA:

Goedgebeur, Jan, Zamfirescu, Carol T.. "Improved bounds for hypohamiltonian graphs." Ars mathematica contemporanea letnik 13. številka 2 (2017) str. 235-257.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-PKP5T2IZ>

Ars mathematica contemporanea
2008-
(Zbirni zapis)