On almost hypohamiltonian graphs

zbMATH Open1417.05114arXiv1606.06577MaRDI QIDQ5226849FDOQ5226849

Authors: Jan Goedgebeur, Carol T. Zamfirescu 

Publication date: 1 August 2019

Abstract: 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 $vew$ 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.

Full work available at URL: https://arxiv.org/abs/1606.06577

Recommendations

• On hypohamiltonian and almost hypohamiltonian graphs
• Hypohamiltonian planar cubic graphs with girth 5
• Improved bounds for hypo-Hamiltonian graphs
• Planar Hypohamiltonian Graphs on 40 Vertices
• On cubic planar hypohamiltonian and hypotraceable graphs

zbMATH Keywords

cubic graphplanar graphexhaustive generationHamiltonian graphalmost hypo-Hamiltonian graphhypo-Hamiltonian graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45)

Cited In (17)

• Title not available (Why is that?)
• On graphs in which the Hoffman bound for cocliques equals the Cvetcovich bound
• Alternating maps on Hatcher–Thurston graphs
• On cubic planar hypohamiltonian and hypotraceable graphs
• Gallai's question and constructions of almost hypotraceable graphs
• Seven problems on hypohamiltonian and almost hypohamiltonian graphs
• Title not available (Why is that?)
• Cubic vertices in planar hypohamiltonian graphs
• On hypohamiltonian and almost hypohamiltonian graphs
• Hypohamiltonian planar cubic graphs with girth 5
• On minimum leaf spanning trees and a criticality notion
• Snarks, hypohamiltonian graphs and non-supereulerian graphs
• The last subconstituent of the Hemmeter graph
• Structural and computational results on platypus graphs
• Non-Hamiltonian graphs in which every edge-contracted subgraph is Hamiltonian
• Generation and new infinite families of \(K_2\)-hypohamiltonian graphs
• Improved bounds for hypo-Hamiltonian graphs

This page was built for publication: On almost hypohamiltonian graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5226849)