Article ID Journal Published Year Pages File Type
6423669 Electronic Notes in Discrete Mathematics 2016 6 Pages PDF
Abstract

A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex deleted subgraphs of G are hamiltonian/traceable. Until now all hypotraceable graphs were constructed using hypohamiltonian graphs; extending a method of Thomassen [C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Mathematics 9 (1974), 91-96] we present a construction that uses so-called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex deleted subgraphs are hamiltonian with exactly one exception). As an application, we construct a planar hypotraceable graph of order 138, improving the best known bound of 154 [M. Jooyandeh, B. D. McKay, P. R. J. Östergård, V. H. Pettersson, C. T. Zamfirescu, Planar Hypohamiltonian Graphs on 40 Vertices, J. Graph Theory DOI: 10.1002/jgt.22015 (2016)]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,