arXiv Analytics

Sign in

arXiv:1712.05158 [math.CO]AbstractReferencesReviewsResources

Structural and computational results on platypus graphs

Jan Goedgebeur, Addie Neyt, Carol T. Zamfirescu

Published 2017-12-14Version 1

A platypus graph is a non-hamiltonian graph for which every vertex-deleted subgraph is traceable. They are closely related to families of graphs satisfying interesting conditions regarding longest paths and longest cycles, for instance hypohamiltonian, leaf-stable, and maximally non-hamiltonian graphs. In this paper, we first investigate cubic platypus graphs, covering all orders for which such graphs exist: in the general and polyhedral case as well as for snarks. We then present (not necessarily cubic) platypus graphs of girth up to 16---whereas no hypohamiltonian graphs of girth greater than 7 are known---and study their maximum degree, generalising two theorems of Chartrand, Gould, and Kapoor. Using computational methods, we determine the complete list of all non-isomorphic platypus graphs for various orders and girths. Finally, we address two questions raised by the third author in [J. Graph Theory \textbf{86} (2017) 223--243].

Related articles: Most relevant | Search more
arXiv:2106.13372 [math.CO] (Published 2021-06-25)
Hamiltonian Paths in Non-Hamiltonian Graphs
arXiv:1412.4247 [math.CO] (Published 2014-12-13)
Searching for knights and spies: a majority/minority game
arXiv:2307.01648 [math.CO] (Published 2023-07-04)
On the structural and combinatorial properties in 2-swap word permutation graphs