Improved bounds for hypohamiltonian graphs

Goedgebeur, Jan; Zamfirescu, Carol

Improved bounds for hypohamiltonian graphs

Jan Goedgebeur UGent and Carol Zamfirescu UGent (2017) ARS MATHEMATICA CONTEMPORANEA. 13(2). p.235-257

Mark

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: http://hdl.handle.net/1854/LU-8512918

author

Jan Goedgebeur UGent and Carol Zamfirescu UGent

organization

Department of Applied mathematics, computer science and statistics

year

2017

type

journalArticle (original)

publication status

published

subject

Mathematics and Statistics

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

issue

pages

235 - 257

Web of Science type

Article

Web of Science id

000396845400001

ISSN

1855-3966

language

English

UGent publication?

yes

classification

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.