Geodesic
Improved bounds for hypohamiltonian graphs
Ars Mathematica Contemporanea, Tome 13 (2017) no. 2, pp. 235-257.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

A graph G is hypohamiltonian if G is non-hamiltonian and G − v is hamiltonian for every v ∈ 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 78.
DOI : 10.26493/1855-3974.1044.eaa
Keywords: Hamiltonian, hypohamiltonian, planar, girth, cubic graph, exhaustive generation 
@article{10_26493_1855_3974_1044_eaa,
     author = {Jan Goedgebeur and Carol T. Zamfirescu},
     title = {Improved bounds for hypohamiltonian graphs},
     journal = {Ars Mathematica Contemporanea},
     pages = {235--257},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2017},
     doi = {10.26493/1855-3974.1044.eaa},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1044.eaa/}
}
TY  - JOUR
AU  - Jan Goedgebeur
AU  - Carol T. Zamfirescu
TI  - Improved bounds for hypohamiltonian graphs
JO  - Ars Mathematica Contemporanea
PY  - 2017
SP  - 235
EP  - 257
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1044.eaa/
DO  - 10.26493/1855-3974.1044.eaa
LA  - en
ID  - 10_26493_1855_3974_1044_eaa
ER  - 
%0 Journal Article
%A Jan Goedgebeur
%A Carol T. Zamfirescu
%T Improved bounds for hypohamiltonian graphs
%J Ars Mathematica Contemporanea
%D 2017
%P 235-257
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1044.eaa/
%R 10.26493/1855-3974.1044.eaa
%G en
%F 10_26493_1855_3974_1044_eaa
Jan Goedgebeur; Carol T. Zamfirescu. Improved bounds for hypohamiltonian graphs. Ars Mathematica Contemporanea, Tome 13 (2017) no. 2, pp. 235-257. doi : 10.26493/1855-3974.1044.eaa. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1044.eaa/

Cité par Sources :