Geodesic
On almost hypohamiltonian graphs
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4

Voir la notice de l'article provenant de la source Episciences

A graph $G$ is almost hypohamiltonian (a.h.) if $G$ is non-hamiltonian, there exists a vertex $w$ in $G$ such that $G - w$ is non-hamiltonian, and $G - v$ is hamiltonian for every vertex $v \ne w$ in $G$. The second author asked in [J. Graph Theory 79 (2015) 63--81] for all orders for which a.h. graphs exist. Here we solve this problem. To this end, we present a specialised algorithm which generates complete sets of a.h. graphs for various orders. Furthermore, we show that the smallest cubic a.h. graphs have order 26. We provide a lower bound for the order of the smallest planar a.h. graph and improve the upper bound for the order of the smallest planar a.h. graph containing a cubic vertex. We also determine the smallest planar a.h. graphs of girth 5, both in the general and cubic case. Finally, we extend a result of Steffen on snarks and improve two bounds on longest paths and longest cycles in polyhedral graphs due to Jooyandeh, McKay, {\"O}sterg{\aa}rd, Pettersson, and the second author. 
@article{DMTCS_2019_21_4_a2,
     author = {Goedgebeur, Jan and Zamfirescu, Carol T.},
     title = {On almost hypohamiltonian graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2019},
     doi = {10.23638/DMTCS-21-4-5},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-5/}
}
TY  - JOUR
AU  - Goedgebeur, Jan
AU  - Zamfirescu, Carol T.
TI  - On almost hypohamiltonian graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-5/
DO  - 10.23638/DMTCS-21-4-5
LA  - en
ID  - DMTCS_2019_21_4_a2
ER  - 
%0 Journal Article
%A Goedgebeur, Jan
%A Zamfirescu, Carol T.
%T On almost hypohamiltonian graphs
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-4-5/
%R 10.23638/DMTCS-21-4-5
%G en
%F DMTCS_2019_21_4_a2
Goedgebeur, Jan; Zamfirescu, Carol T. On almost hypohamiltonian graphs. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 4. doi: 10.23638/DMTCS-21-4-5

Cité par Sources :