Ghent University Academic Bibliography

Advanced

Improved bounds for hypohamiltonian graphs

Jan Goedgebeur UGent and Carol Zamfirescu UGent (2017) ARS MATHEMATICA CONTEMPORANEA. 13(2). p.235-257
abstract
A graph G is hypohamiltonian if G is non-hamiltonian and G - nu is hamiltonian for every nu is an element of 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.
Please use this url to cite or link to this publication:
author
organization
year
type
journalArticle (original)
publication status
published
subject
keyword
Hamiltonian, hypohamiltonian, planar, girth, cubic graph, exhaustive generation, CUBIC PLANAR GRAPHS, HYPOTRACEABLE GRAPHS, FAST GENERATION, VERTICES
journal title
ARS MATHEMATICA CONTEMPORANEA
Ars Math. Contemp.
volume
13
issue
2
pages
235 - 257
Web of Science type
Article
Web of Science id
000396845400001
ISSN
1855-3966
language
English
UGent publication?
yes
classification
A1
copyright statement
I have retained and own the full copyright for this publication
id
8512918
handle
http://hdl.handle.net/1854/LU-8512918
date created
2017-03-07 12:12:35
date last changed
2017-07-25 12:43:18
@article{8512918,
  abstract     = {A graph G is hypohamiltonian if G is non-hamiltonian and G - nu is hamiltonian for every nu is an element of 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.},
  author       = {Goedgebeur, Jan and Zamfirescu, Carol},
  issn         = {1855-3966},
  journal      = {ARS MATHEMATICA CONTEMPORANEA},
  keyword      = {Hamiltonian,hypohamiltonian,planar,girth,cubic graph,exhaustive generation,CUBIC PLANAR GRAPHS,HYPOTRACEABLE GRAPHS,FAST GENERATION,VERTICES},
  language     = {eng},
  number       = {2},
  pages        = {235--257},
  title        = {Improved bounds for hypohamiltonian graphs},
  volume       = {13},
  year         = {2017},
}

Chicago
Goedgebeur, Jan, and Carol Zamfirescu. 2017. “Improved Bounds for Hypohamiltonian Graphs.” Ars Mathematica Contemporanea 13 (2): 235–257.
APA
Goedgebeur, J., & Zamfirescu, C. (2017). Improved bounds for hypohamiltonian graphs. ARS MATHEMATICA CONTEMPORANEA, 13(2), 235–257.
Vancouver
1.
Goedgebeur J, Zamfirescu C. Improved bounds for hypohamiltonian graphs. ARS MATHEMATICA CONTEMPORANEA. 2017;13(2):235–57.
MLA
Goedgebeur, Jan, and Carol Zamfirescu. “Improved Bounds for Hypohamiltonian Graphs.” ARS MATHEMATICA CONTEMPORANEA 13.2 (2017): 235–257. Print.