2023/11/17 by Jan Goedgebeur, Goedgebeur, Jan, Jarne Renders +3 · 1 citation
Computer Science · #05C10 #05C30 #05C38 #05C45 #05C76 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2311.10593
openalex publication_date 2023/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present an algorithm which can generate all pairwise non-isomorphic K2-hypohamiltonian graphs, i.e. non-hamiltonian graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph, of a given order. We introduce new bounding criteria specifically designed for K2-hypohamiltonian graphs, allowing us to improve upon earlier computational results. Specifically, we characterise the orders for which K2-hypohamiltonian graphs exist and improve existing lower bounds on the orders of the smallest planar and the smallest bipartite K2-hypohamiltonian graphs. Furthermore, we describe a new operation for creating K2-hypohamiltonian graphs that preserves planarity under certain conditions and use it to prove the existence of a planar K2-hypohamiltonian graph of order n for every integer n≥ 134. Additionally, motivated by a theorem of Thomassen on hypohamiltonian graphs, we show the existence K2-hypohamiltonian graphs with large maximum degree and size.