We show that there exists an infinite family of cubic 2-connected non-hamiltonian graphs with girth at least 5 containing a unique longest cycle.

Kratsch, Lehel, and Müller define a hereditary graph class 𝒢 to have the Steiner-Deogun property if for every G ∈ 𝒢, the graph G is hamiltonian if and only if all of G's vertex-deleted subgraphs are traceable. A platypus is a non-hamiltonian graph in which every vertex-deleted subgraph is traceable. We prove a series of results on the Steiner-Deogun property and platypus graphs. For instance, although neither planar nor bipartite graphs satisfy the Steiner-Deogun property, it remains open whether planar bipartite graphs do. Motivated by this question, we show that for every tree T there exists a planar platypus G such that T is an induced subgraph of G. On the other hand, there exists an infinite family of planar graphs each member of which is not an induced subgraph of any planar platypus.

We give an enumerative version of Seyffarth's theorem on small cycle double covers in planar 4-connected graphs. We then count cycle double covers of certain sizes in antiprisms and related graphs, giving a surprisingly small upper bound. Thereafter we treat cubic graphs, strengthening a lemma of Hušek and Šámal on the enumeration of cycle double covers, and, motivated by a conjecture of Bondy, give an alternative proof of the result that every planar 2-connected cubic graph on n > 4 vertices has a cycle double cover of size at most n/2. Some of our results are accompanied by a version thereof for cycle double covers containing no cycle twice.

In a given graph, a HIST is a spanning tree without 2-valent vertices. Motivated by developing a better understanding of HIST-free graphs, i.e. graphs containing no HIST, in this article's first part we study HIST-critical graphs, i.e. HIST-free graphs in which every vertex-deleted subgraph does contain a HIST (e.g. a triangle). We give an almost complete characterisation of the orders for which these graphs exist and present an infinite family of planar examples which are 3-connected and in which nearly all vertices are 4-valent. This leads naturally to the second part in which we investigate planar 4-regular graphs with and without HISTs, motivated by a conjecture of Malkevitch, which we computationally verify up to order 22. First we enumerate HISTs in antiprisms, whereafter we present planar 4-regular graphs with and without HISTs, obtained via line graphs.

In the seventies, Mikhail Gromov introduced a natural concept for measuring distance between metric spaces. We use his concept, endowing the space of all finite connected graphs with the Gromov-Hausdorff metric, and prove a series of observations concerning this space. Thus, we also investigate here graphs of graphs.

We devise several new upper bounds for shortness parameters of regular polyhedra and of the polyhedra that have two vertex degrees, and relate these to each other. Grünbaum and Walther showed that quartic polyhedra have shortness exponent at most log 22/log 23. This was subsequently improved by Harant to log 16/log 17, which holds even when all faces are either triangles or of length k, for infinitely many k. We complement Harant's result by strengthening the Grünbaum-Walther bound to log 4/log 5, and showing that this bound even holds for the family of quartic polyhedra with faces of length at most 7. Furthermore, we prove that for every 4 ≤ k ≤ 8 the shortness exponent of the polyhedra having only vertices of degree 3 or k is at most log 5/log 7. Motivated by work of Ewald and Reynolds, we show that polyhedral quadrangulations with maximum degree at most 5 have shortness coefficient at most 30/37. Finally, we define path analogues for shortness parameters, and propose first dependencies between these measures.

Let G be a connected graph and L(G) the set of all integers k such that G contains a spanning tree with exactly k leaves. We show that for a connected graph G, the set L(G) is contiguous. It follows from work of Chen, Ren, and Shan that every connected and locally connected n-vertex graph – this includes triangulations – has a spanning tree with at least n/2 + 1 leaves, so by a classic theorem of Whitney and our result, in any plane 4-connected n-vertex triangulation one can find for any integer k which is at least 2 and at most n/2 + 1 a spanning tree with exactly k leaves (and each of these trees can be constructed in polynomial time). We also prove that there exist infinitely many n such that there is a plane 4-connected n-vertex triangulation containing a spanning tree with 2n/3 leaves, but no spanning tree with more than 2n/3 leaves.

We investigate the minimum number of cycles of specified lengths in planar n-vertex triangulations G. It is proven that this number is Ω(n) for any cycle length at most 3 + max { rad(G*), ((n − 3)/2)^log₃2 }, where rad(G*) denotes the radius of the triangulation's dual, which is at least logarithmic but can be linear in the order of the triangulation. We also show that there exist planar hamiltonian n-vertex triangulations containing O(n) many k-cycles for any k ∈ { n − $\sqrt[5]{\mathrm{<i><font\; face="palatino\; linotype"\; size="3">n</font></i>}}$, ..., $$n }. Furthermore, we prove that planar 4-connected n-vertex triangulations contain Ω(n) many k-cycles for every k ∈ { 3, ..., n }, and that, under certain additional conditions, they contain Ω(n²) k-cycles for many values of k, including n.

In this note it is proven that there exist infinitely many positive integers a and b such that the Cartesian product of a directed cycle of length 2a and a directed cycle of length 2b is non-Hamiltonian. In particular, the Cartesian product of an 880-dicycle and a 4368-dicycle is non-Hamiltonian. We also prove that there is no such graph on fewer than 880 × 4368 = 3,843,840 vertices, which is rather astonishing.

After our paper appeared, we became aware of an article authored by Erdős and Trotter and published in J. Graph Theory 2 (1978) 137–42, see here. In their Example 2 they observe that 880 × 4368 is the order of a smallest example. On the one hand, we should have looked at previous work more carefully. On the other hand, they give as reason for why the value above is the smallest, the fact that 8 is the smallest q. However, one cannot immediately deduce that the smallest order is accomplished by the smallest d. Indeed, we checked that the smallest order for q = 32 is larger than the smallest orders for both q = 33 and q = 35. In our paper, we prove that 3,843,840 is the smallest order (and { 880, 4368 } is the unique pair attaining it).

Inspired by Sheehan's conjecture that no 4-regular graph contains exactly one hamiltonian cycle, we prove results on hamiltonian cycles in regular graphs and nearly regular graphs. We fully disprove a conjecture of Haythorpe on the minimum number of hamiltonian cycles in regular hamiltonian graphs, thereby extending a result of Zamfirescu, as well as correct and complement Haythorpe's computational enumerative results from [Experim. Math. 27 (2018) 426–30]. Thereafter, we use the Lovász Local Lemma to extend Thomassen's independent dominating set method. This extension allows us to find a second hamiltonian cycle that inherits linearly many edges from the first hamiltonian cycle. Regarding the limitations of this method, we answer a question of Haxell, Seamone, and Verstraete, and settle the first open case of a problem of Thomassen by showing that for k ∊ { 5, 6 } there exist infinitely many k-regular hamiltonian graphs having no independent dominating set with respect to a prescribed hamiltonian cycle. Motivated by an observation of Aldred and Thomassen, we prove that for every κ ∊ { 2, 3 } and any positive integer k, there are infinitely many non-regular graphs of connectivity κ containing exactly one hamiltonian cycle and in which every vertex has degree 3 or 2k.

The graph6 format is for storing graphs in a compact manner, using only printable ASCII characters—these include (but are not limited to) the letters in the English alphabet, in both lower and upper case. While the vast majority of graphs have graph6 strings such as IheA@GUAo (this yields Petersen's graph), there exist graphs whose graph6 strings are identical to words in the English language. The purpose of this note is to present an example of such a string, as well as a characterisation of words that appear as graph6 strings.

Thomassen proved in 1978 that if in an n-vertex planar graph G whose minimum degree is at least 4 all vertex-deleted subgraphs of G are hamiltonian, then G is hamiltonian. It was recently shown that in the preceding sentence, “all” can be replaced by “at least n − 5”. In this note we prove that, if 3-connectedness is assumed, it cannot be replaced by n − 24 (or any other integer greater than 24). The exact threshold remains unknown. We show that the same conclusion holds for triangulations and use computational means to prove that, under a natural restriction, this result is best possible.

We present an algorithm which can generate all pairwise non-isomorphic K₂-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 especially designed for K₂-hypohamiltonian graphs, allowing us to improve upon earlier computational results. Specifically, we characterise the orders for which K₂-hypohamiltonian graphs exist and improve existing lower bounds on the orders of the smallest planar and the smallest bipartite K₂-hypohamiltonian graphs. Furthermore, we describe a new operation for creating K₂-hypohamiltonian graphs that preserves planarity under certain conditions and use it to prove the existence of a planar K₂-hypohamiltonian graph of order n for every integer n ≥ 134. Additionally, motivated by a theorem of Thomassen on hypohamiltonian graphs, we show the existence K₂-hypohamiltonian graphs with large maximum degree and size.

Given an infinite family of graphs, its domination ratio is the smallest real k such that for every large enough graph in the family, the ratio between its domination number and order is at most k. We present bounds for the domination ratios of various families of triangulated discs. For instance, it is shown that the domination ratio of triangulated discs of minimum degree 3 is at least 3/10, thereby disproving a conjecture of Tokunaga. We also give a natural extension of a theorem on the domination number of maximal outerplane graphs, proven by Campos and Wakabayashi, and independently Tokunaga. Motivated by the Matheson-Tarjan Conjecture, we discuss observations on dominating triangulations via Jackson-Yu decomposition trees as well as an approach on how to efficiently dominate, given a triangulation, many large subtriangulations thereof. Throughout the paper, results are accompanied by computational experiments.

In this paper, we use theoretical and computational tools to continue our investigation of K₂-hamiltonian graphs, that is, graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph, and their interplay with K₁-hamiltonian graphs, that is, graphs in which every vertex-deleted subgraph is hamiltonian. Perhaps surprisingly, there exist graphs that are both K₁- and K₂-hamiltonian, yet non-hamiltonian, for example, the Petersen graph. Grünbaum conjectured that every planar K₁-hamiltonian graph must itself be hamiltonian; Thomassen disproved this conjecture. Here we show that even planar graphs that are both K₁- and K₂-hamiltonian need not be hamiltonian, and that the number of such graphs grows at least exponentially. Motivated by results of Aldred, McKay, and Wormald, we determine for every integer n that is not 14 or 17 whether there exists a K₂-hypohamiltonian, that is non-hamiltonian and K₂-hamiltonian, graph of order n, and characterise all orders for which such cubic graphs and such snarks exist. We also describe the smallest cubic planar graph which is K₂-hypohamiltonian, as well as the smallest planar K₂-hypohamiltonian graph of girth 5. We conclude with open problems and by correcting two inaccuracies from the first article.

Grünbaum conjectured that for any integer k ≥ 2, there exists no n-vertex graph G of circumference n − k in which the removal of any k vertices from G yields a hamiltonian graph. We show that for any positive integers c and k there is an infinite family of c-connected graphs of circumference k less than their order, in which the limit (as the graphs' order tends to infinity) of the ratio between the number of k-vertex sets whose removal yields a hamiltonian graph and the number of all k-vertex sets is 1. Motivated by a question of Katona, Kostochka, Pach, and Stechkin, it is proven that there exists an infinite family of non-hamiltonian graphs of increasing diameter d in which the removal of any two vertices at distance 1 or any distance at least (d + 6)/2 yields a hamiltonian graph.

Tutte proved that every planar 4-connected graph is hamiltonian. Thomassen showed that the same conclusion holds for the superclass of planar graphs with minimum degree at least 4 in which all vertex-deleted subgraphs are hamiltonian. We here prove that if in a planar n-vertex graph with minimum degree at least 4 at least n − 5 vertex-deleted subgraphs are hamiltonian, then the graph contains two hamiltonian cycles, but that for every c < 1 there exists a non-hamiltonian polyhedral n-vertex graph with minimum degree at least 4 containing c n hamiltonian vertex-deleted subgraphs. Furthermore, we study the hamiltonicity of planar triangulations and their vertex-deleted subgraphs as well as Bondy's meta-conjecture, and prove that a polyhedral graph with minimum degree at least 4 in which all vertex-deleted subgraphs are traceable, must itself be traceable.

This note complements results on cycle spectra of planar graphs by investigating the toroidal case. Let k ≥ 3 be an integer and G a cubic graph polyhedrally embedded on the torus with circumference at least k. For k = 3, it follows from Euler's formula that G has some (facial) cycle of length in [3, 6]. For k = 4 or 5, we show that G contains a cycle whose length lies in the interval [k, 12]; and for k > 5, we show that the same holds for the interval [k, 2k + 4]. This is best possible for all k ≥ 4. On the other hand, for any non-negative integer γ there exist 2-connected cubic graphs G of genus γ, arbitrarily large face-width, and with arbitrarily large gaps in their cycle spectrum. The behaviour of cycle spectrum gaps of graphs polyhedrally embedded on surfaces of genus greater than 1 remains largely unknown.

The dual of a polyhedron is a polyhedron—or in graph theoretical terms: the dual of a 3-connected plane graph is a 3-connected plane graph. Astonishingly, except for sufficiently large facewidth, not much is known about the connectivity of the dual on higher surfaces. Are the duals of 3-connected embedded graphs of higher genus 3-connected, too? If not: which connectivity guarantees 3-connectedness of the dual? In this article, we give answers to this and related questions. Among other things, we prove that there is no connectivity that for every genus guarantees the 3-connectedness or 2-connectedness of the dual, and give upper bounds for the minimum genus for which (with c > 2) a c-connected embedded graph with a dual that has a 1- or 2-cut can occur. For the torus, we determine exact values for the connectivity needed to guarantee 3- respectively 2-connectivity of the dual. We prove that already on the torus, we need 6-connectedness to guarantee 3-connectedness of the dual and 4-connectedness to guarantee 2-connectedness of the dual. In the last section, we answer a related question by Plummer and Zha on orientable embeddings of highly connected non-complete graphs.

We investigate 2-planarizing 2-factors, i.e. 2-factors of embedded graphs so that cutting along the cycles of the 2-factor we get two plane graphs where the cycles of the 2-factors are a spanning set of face boundaries in each of the graphs. We will give necessary criteria for an abstract graph to have an embedding with a 2-planarizing 2-factor as well as necessary criteria for embedded graphs to have such a 2-factor. Along the way, we discuss to which degree classical results from planar hamiltonicity theory can be extended in our framework. In addition we present computational results on how common 2-planarizing 2-factors are in small cubic graphs.

Motivated by work of Haythorpe, Thomassen and the author showed that there exists a positive constant c such that there is an infinite family of 4-regular 4-connected graphs, each containing exactly c hamiltonian cycles. We complement this by proving that the same conclusion holds for planar 4-regular 3-connected graphs, although it does not hold for planar 4-regular 4-connected graphs by a result of Brinkmann and Van Cleemput, and that it holds for 4-regular graphs of connectivity 2 with the constant 144 < c, which we believe to be minimal among all hamiltonian 4-regular graphs of sufficiently large order. We then disprove a conjecture of Haythorpe by showing that for every non-negative integer k there is a 5-regular graph on 26 + 6k vertices with 2^k+3 · 3^k+10 hamiltonian cycles. We prove that for every d ≥ 3 there is an infinite family of hamiltonian 3-connected graphs with minimum degree d, with a bounded number of hamiltonian cycles. It is shown that if a 3-regular graph G has a unique longest cycle C, at least two components of G − E(C) have an odd number of vertices on C, and that there exist 3-regular graphs with exactly two such components.

On page 766, at the beginning of Section 3, instead of referring to Table 1 one must refer to Table 3 from [J. Goedgebeur, B. Meersman, and C. T. Zamfirescu, Graphs with few Hamiltonian cycles, Math. Comp. 89 (2020) 965–991].

It is proven that for any integer g ≥ 0 and k ∈ {0, ..., 10}, there exist infinitely many 5-regular graphs of genus g containing a 1-factorisation with exactly k pairs of 1-factors that are perfect, i.e. form a hamiltonian cycle. For g = 0 and k = 10, this settles a problem of Kotzig from 1964. Motivated by Kotzig and Labelle's “marriage” operation, we discuss two gluing techniques aimed at producing graphs of high cyclic edge-connectivity. We prove that there exist infinitely many planar 5-connected 5-regular graphs in which every 1-factorisation has zero perfect pairs. On the other hand, by the Four Colour Theorem and a result of Brinkmann and the first author, every planar 4-connected 5-regular graph satisfying a condition on its hamiltonian cycles has a linear number of 1-factorisations each containing at least one perfect pair. We also prove that every planar 5-connected 5-regular graph satisfying a stronger condition contains a 1-factorisation with at most nine perfect pairs, whence, every such graph admitting a 1-factorisation with ten perfect pairs has at least two edge-Kempe equivalence classes.

Merker conjectured that if k ≥ 2 is an integer and G a 3-connected cubic planar graph of circumference at least k, then the set of cycle lengths of G must contain at least one element of the interval [k, 2k+2]. We here prove that for every even integer k ≥ 6 there is an infinite family of counterexamples.

In 1978 Thomassen asked whether planar hypohamiltonian oriented graphs exist. Infinite families of such graphs have since been described but for infinitely many n it remained an open question whether planar hypohamiltonian oriented graphs of order n exist. In this paper we develop new methods for constructing hypohamiltonian digraphs, which, combined with efficient graph generation algorithms, enable us to fully characterise the orders for which planar hypohamiltonian oriented graphs exist. Our novel methods also led us to discover the planar hypohamiltonian oriented graph of smallest order and size, as well as infinitely many hypohamiltonian orientations of maximal planar graphs. Furthermore, we answer a question related to a problem of Schiermeyer on vertex degrees in hypohamiltonian oriented graphs, and characterise all the orders for which planar hypotraceable oriented graphs exist.

A 2-connected non-hamiltonian graph G is a k-graph if for exactly k < |V(G)| vertices in G, removing such a vertex yields a non-hamiltonian graph. We characterise k-graphs of connectivity 2 and describe structurally interesting examples of such graphs containing no cubic vertex or of minimum degree at least 4, with a special emphasis on the planar case. We prove that there exists a k₀ such that for every k ≥ k₀ infinitely many planar k-graphs of connectivity 2 and minimum degree 4 exist. As a variation of a result of Thomassen, we show that certain planar 3-graphs must contain a cubic vertex.

We prove that there exists an infinite family of 4-regular 4-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles. We do not know if there exists such a family of 5-regular 5-connected Hamiltonian graphs.

Motivated by a conjecture of Grünbaum and a problem of Katona, Kostochka, Pach, and Stechkin, both dealing with non-hamiltonian n-vertex graphs and their (n − 2)-cycles, we investigate K₂-hamiltonian graphs, i.e. graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph. In this first part, we prove structural properties, and show that there exist infinitely many cubic non-hamiltonian K₂-hamiltonian graphs, both of the 3-edge-colourable and the non-3-edge-colourable variety. In fact, cubic K₂-hamiltonian graphs with chromatic index 4 (such as Petersen's graph) are a subset of the critical snarks. On the other hand, it is proven that non-hamiltonian K₂-hamiltonian graphs of any maximum degree exist. Several operations conserving K₂-hamiltonicity are described, one of which leads to the result that there exists an infinite family of non-hamiltonian K₂-hamiltonian graphs in which, asymptotically, a quarter of vertices has the property that removing such a vertex yields a non-hamiltonian graph. We extend a celebrated result of Tutte by showing that every planar K₂-hamiltonian graph with minimum degree at least 4 is hamiltonian. Finally, we investigate K₂-traceable graphs, and discuss open problems.

Proposition 6 in Section 3.2 discusses the so-called dot product in the context of K₂-hamiltonicity. Unfortunately, the third and fourth paragraphs of its “proof” contain errors. Corrections have been added in Section 4 of the second paper in this series, see article № 57. A minor issue with Lemma 3 in Section 3.1 is also corrected.

Špacapan recently showed that there exist 3-polytopes with non-hamiltonian prisms, disproving a conjecture of Rosenfeld and Barnette. By adapting Špacapan's approach we strengthen his result in several directions. We prove that there exists an infinite family of counterexamples to the Rosenfeld-Barnette conjecture, each member of which has maximum degree 37 and girth 4. We also show that for any given 3-polytope H there is a counterexample containing H as an induced subgraph. This yields an infinite family of non-hamiltonian 4-polytopes in which the proportion of quartic vertices tends to 1. However, Barnette's conjecture stating that every 4-polytope in which all vertices are quartic is hamiltonian still stands. Finally, we prove that the Grünbaum-Walther shortness coefficient of the family of all prisms of 3-polytopes is at most 59/60.

A graph G is perihamiltonian if G itself is non-hamiltonian, yet every edge-contracted subgraph of G is hamiltonian. These graphs form a superclass of the hypohamiltonian graphs. By applying a recent result of Wiener on path-critical graphs, we prove the existence of infinitely many perihamiltonian graphs of connectivity k for any k ≥ 2. Furthermore, we show that every planar perihamiltonian graph of connectivity k contains a vertex of degree k. This strengthens the theorem of Thomassen stating that every planar hypohamiltonian graph contains a cubic vertex, and entails that if in a polyhedral graph of minimum degree at least 4 the set of vertices whose removal yields a non-hamiltonian graph is independent, the graph itself must be hamiltonian. Although it remains an open problem whether every planar hypohamiltonian graph contains adjacent cubic vertices, we here prove that there are infinitely many polyhedral perihamiltonian graphs for which this is not the case.

A spider is a tree with at most one branch (a vertex of degree at least 3) centred at the branch if it exists, and centred at any vertex otherwise. A graph G is arachnoid if for any vertex v of G, there exists a spanning spider of G centred at v—in other words: there are spiders everywhere! Hypotraceable graphs are non-traceable graphs in which all vertex-deleted subgraphs are traceable. Gargano, Hammar, Hell, Stacho, and Vaccaro [Discrete Math. 285 (2004) 83–95] defined arachnoid graphs as natural generalisations of traceable graphs and asked for the existence of arachnoid graphs that are (i) non-traceable and non-hypotraceable, or (ii) in which some vertex is the centre of only spiders with more than three legs. An affirmative answer to (ii) implies an affirmative answer to (i). While non-traceable, non-hypotraceable arachnoid graphs were described in [J. Graph Theory 84 (2017) 443–59], (ii) remained open. In this paper we give an affirmative answer to this question and discuss spanning spiders whose legs must have some minimum length.

A graph is 1-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1-planar. For a 3-connected locally maximal 1-planar graph G, we show the existence of a spanning 3-connected planar subgraph and prove that G is hamiltonian if G has at most three 3-vertex-cuts, and that G is traceable if G has at most four 3-vertex-cuts. Moreover, infinitely many 5-connected 1-planar non-traceable graphs are presented.

In this note, we consider triangulations of the plane. Ozeki and the second author asked whether there are non-hamiltonian 1-tough triangulations in which every two separating triangles are disjoint. We answer this question in the affirmative and strengthen a result of Nishizeki by proving that there are infinitely many non-hamiltonian 1-tough triangulations with pairwise disjoint separating triangles.

The minimum leaf number of a connected non-hamiltonian graph G is the number of leaves of a spanning tree of G with the fewest leaves among all spanning trees of G. Based on this quantity, Wiener introduced leaf-stable and leaf-critical graphs, concepts which generalise hypotraceability and hypohamiltonicity. In this article, we present new methods to construct leaf-stable and leaf-critical graphs and study their properties. Furthermore, we improve several bounds related to these families of graphs. These extend previous results of Horton, Thomassen, and Wiener.

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 86 (2017) 223–43].

Grünbaum and Malkevitch proved that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most 76/77. Recently, this was improved to 359/366 (< 52/53) and the question was raised whether this can be strengthened to 41/42, a natural bound inferred from one of the Faulkner-Younger graphs. We prove that the shortness coefficient of cyclically 4-edge-connected cubic planar graphs is at most 37/38 and that we also get the same value for cyclically 4-edge-connected cubic graphs of genus g for any prescribed genus g ≥ 0. We also show that 45/46 is an upper bound for the shortness coefficient of cyclically 4-edge-connected cubic graphs of genus g with face lengths bounded above by some constant larger than 22 for any prescribed g ≥ 0.

We describe an algorithm for the exhaustive generation of non-isomorphic graphs with a given number k ≥ 0 of hamiltonian cycles, which is especially efficient for small k. Our main findings, combining applications of this algorithm and existing algorithms with new theoretical results, revolve around graphs containing exactly one hamiltonian cycle (1H) or exactly three hamiltonian cycles (3H). Motivated by a classic result of Smith and recent work of Royle, we show that there exist nearly cubic 1H graphs of order n iff n ≥ 18 is even. This gives the strongest form of a theorem of Entringer and Swart, and sheds light on a question of Fleischner originally settled by Seamone. We prove equivalent formulations of the conjecture of Bondy and Jackson that every planar 1H graph contains two vertices of degree 2, verify it up to order 16, and show that its toric analogue does not hold. We treat Thomassen's conjecture that every hamiltonian graph of minimum degree at least 3 contains an edge such that both its removal and its contraction yield hamiltonian graphs. We also verify up to order 21 the conjecture of Sheehan that there is no 4-regular 1H graph. Extending work of Schwenk, we describe all orders for which cubic 3H triangle-free graphs exist. We verify up to order 48 Cantoni's conjecture that every planar cubic 3H graph contains a triangle, and show that for every k that is 0 or at least 4 there exists a planar cyclically 4-edge-connected cubic graph with exactly k hamiltonian cycles. Finally, complementing work of Sheehan on 1H graphs of maximum size, we determine the maximum size of graphs containing exactly one hamiltonian path and give, for every order n, the exact number of such graphs on n vertices and of maximum size.

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 v ≠ w 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, Östergård, Pettersson, and the second author.

In 1956, Tutte showed that every planar 4-connected graph is hamiltonian. In this article, we will prove that even if we relax the prerequisites on the polyhedra from 4-connected to containing at most three 3-cuts, hamiltonicity is still guaranteed. This also strengthens a theorem of Jackson and Yu, who have shown the result for the subclass of triangulations. We also prove that polyhedra with at most four 3-cuts have a hamiltonian path. It is well known that for each k ≥ 6 non-hamiltonian polyhedra with k 3-cuts exist. We give computational results on lower bounds on the order of a possible non-hamiltonian polyhedron for the remaining open cases of polyhedra with four or five 3-cuts.

We describe an infinite family of 2-connected graphs, each of which has the property that the intersection of all longest cycles is empty. In particular, we present such graphs with circumference 10, 13, and 16. This settles a question of van Aardt et al. [Discrete Appl. Math. 186 (2015) 251–9] concerning the existence of such graphs for all but one case, namely circumference 11. We also present a 2-connected graph of circumference 11 in which all but one vertex are avoided by some longest cycle.

Thomassen showed in 1978 that every planar hypohamiltonian graph contains a cubic vertex. Equivalently, a planar graph with minimum degree at least 4 in which every vertex-deleted subgraph is hamiltonian, must be itself hamiltonian. By applying work of Brinkmann and the author, we extend this result in three directions. We prove that (i) every planar hypohamiltonian graph contains at least four cubic vertices, (ii) every planar almost hypohamiltonian graph contains a cubic vertex which is not the exceptional vertex (solving a problem of the author raised in [J. Graph Theory 79 (2015) 63–81]), and (iii) every hypohamiltonian graph with crossing number 1 contains a cubic vertex. Furthermore, we settle a recent question of Thomassen by proving that asymptotically the ratio of the minimum number of cubic vertices to the order of a planar hypohamiltonian graph vanishes.

A graph is called maximally non-hamiltonian if it is non-hamiltonian, yet for any two non-adjacent vertices there exists a hamiltonian path between them. In this paper, we naturally extend the concept to directed graphs and bound their size from below and above. Our results on the lower bound constitute our main contribution, while the upper bound can be obtained using a result of Lewin, but we give here a different proof. We describe digraphs attaining the upper bound, but whether our lower bound can be improved remains open.

We generalize Grinberg's hamiltonicity criterion for planar graphs. To this end, we first prove a technical theorem for embedded graphs. As a special case of a corollary of this theorem we obtain Zaks' extension of Grinberg's Criterion (which encompasses earlier work of Gehner and Shimamoto), but the result also implies Grinberg's formula in its original form in a much broader context. Further implications are a short proof for a slightly strengthened criterion of Lewis bounding the length of a shortest closed walk from below as well as a generalization of a theorem due to Bondy and Häggkvist.

A seminal theorem of Tutte states that planar 4-connected graphs are hamiltonian. Applying a result of Thomas and Yu, one can show that every 4-connected graph with crossing number 1 is hamiltonian. In this paper, we continue along this path and prove the titular statement. We also discuss the traceability and hamiltonicity of 3-connected graphs with small crossing number and few 3-cuts, and present applications of our results.

Invoking Steinitz' Theorem, in the following a polyhedron shall be a planar 3-connected graph. From around 1880 till 1946 Tait's conjecture that cubic polyhedra are hamiltonian was thought to hold—its truth would have implied the Four Colour Theorem. However, Tutte gave a counterexample. We briefly survey the ensuing hunt for the smallest non-hamiltonian cubic polyhedron, the Lederberg-Bosák-Barnette graph, and prove that there exists a non-hamiltonian essentially 4-connected cubic polyhedron of order n if and only if n ≥ 42. This extends work of Aldred, Bau, Holton, and McKay. We then present our main results which revolve around the quartic case: combining a novel theoretical approach for determining non-hamiltonicity in (not necessarily planar) graphs of connectivity 3 with computational methods, we dramatically improve two bounds due to Zaks. In particular, we show that the smallest non-hamiltonian quartic polyhedron has at least 35 and at most 39 vertices, thereby almost reaching a quartic analogue of a famous result of Holton and McKay. As an application of our results, we obtain that the shortness coefficient of the family of all quartic polyhedra does not exceed 5/6. The paper ends with a discussion of the quintic case in which we tighten a result of Owens.

The main finding of this paper was mentioned in the September 2019 Feature Column of the American Mathematical Society, written by Joseph Malkevitch.

We give an overview of the most important techniques and results concerning the hamiltonian properties of planar 3-connected graphs with few 3-vertex-cuts. In this context, we also discuss planar triangulations and their decomposition trees. We observe an astonishing similarity between the hamiltonian behavior of planar triangulations and planar 3-connected graphs. In addition to surveying, (i) we give a unified approach to constructing non-traceable, non-hamiltonian, and non-hamiltonian-connected triangulations, and show that planar 3-connected graphs (ii) with at most one 3-vertex-cut are hamiltonian-connected, and (iii) with at most two 3-vertex-cuts are 1-hamiltonian, filling two gaps in the literature. Finally, we discuss open problems and conjectures.

We prove the titular statement. This settles a problem of Chvátal from 1973 and encompasses earlier results of Thomassen, who showed it for K₃, and Collier and Schmeichel, who proved it for bipartite graphs. We also show that for every outerplanar graph there exists a planar hypohamiltonian graph containing it as an induced subgraph.

Consider a graph G in which the longest path has order |V(G)| − 1. We denote the number of vertices v in G such that G − v is non-traceable with t_G. Gallai asked in 1966 whether, in a connected graph, the intersection of all longest paths is non-empty. Walther showed that, in general, this is not true. In a graph G in which the longest path has |V(G)| − 1 vertices, the answer to Gallai's question is positive iff t_G ≠ 0. In this article we study almost hypotraceable graphs, which constitute the extremal case t_G = 1. We give structural properties of these graphs, establish construction methods for connectivities 1 through 4, show that there exists a cubic 3-connected such graph of order 28, and draw connections to works of Thomassen and Gargano et al.

In 1996 Böhme, Harant, and Tkáč asked whether there exists a non-hamiltonian triangulation with the property that any two of its separating triangles lie at distance at least 1. Two years later, Böhme and Harant answered this in the affirmative, showing that for any non-negative integer d there exists a non-hamiltonian triangulation with seven separating triangles every two of which lie at distance at least d. In this note we prove that the result holds if we replace seven with six, remarking that no non-hamiltonian triangulation with fewer than six separating triangles is known.

A graph G is hypohamiltonian if G is non-hamiltonian and for every vertex v in G, the graph G − v is hamiltonian. McKay asked in [J. Graph Theory 85 (2017) 7–11] whether infinitely many planar cubic hypohamiltonian graphs of girth 5 exist. We settle this question affirmatively.

We study the maximum number of congruent triangles in finite arrangements of ℓ lines in the Euclidean plane. Denote this number by  f (ℓ). We show that  f (5) = 5 and that the construction realizing this maximum is unique,  f (6) = 8, and  f (7) = 14. We also discuss for which integers c there exist arrangements on ℓ lines with exactly c congruent triangles. In parallel, we treat the case when the triangles are faces of the plane graph associated to the arrangement (i.e. the interior of the triangle has empty intersection with every line in the arrangement). Lastly, we formulate four conjectures.

We discuss an omission in the statement and proof of Fiorini's 1983 theorem on hypohamiltonian snarks and present a version of this theorem which is more general in several ways. Using Fiorini’s erroneous result, Steffen showed that hypohamiltonian snarks exist for some n ≥ 10 and each even n ≥ 92. We rectify Steffen's proof by providing a correct demonstration of a technical lemma on flower snarks, which might be of separate interest. We then strengthen Steffen's theorem to the strongest possible form by determining all orders for which hypohamiltonian snarks exists. This also strengthens a result of Máčajová and Škoviera. Finally, we verify a conjecture of Steffen on hypohamiltonian snarks up to 36 vertices.

We call a graph G a platypus if G is non-hamiltonian, and for any vertex v in G, the graph G − v is traceable. Every hypohamiltonian and every hypotraceable graph is a platypus, but there exist platypuses which are neither hypohamiltonian nor hypotraceable. Among other things, we give a sharp lower bound on the size of a platypus depending on its order, draw connections to other families of graphs, and solve two open problems of Wiener. We also prove that there exists a k-connected platypus for every k ≥ 2.

A graph G is hypohamiltonian if G is non-hamiltonian and G − v is hamiltonian for every v ∈ 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.

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer-aided generation of certain families of planar graphs with girth 4 and a fixed number of 4-faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest hypohamiltonian planar graph of girth 5 has 45 vertices.

We reflect upon an analogue of the cut locus, a notion classically studied in Differential Geometry, for finite graphs. The cut locus C(x) of a vertex x shall be the graph induced by the set of all vertices y with the property that no shortest path between x and z, z ≠ y, contains y. The cut locus coincides with the graph induced by the vertices realizing the local maxima of the distance function. The function F mapping a vertex x to F(x), the set of global maxima of the distance function from x, is the farthest point mapping. Among other things, we observe that if for a vertex x, C(x) is connected, then C(x) is the graph induced by F(x), and prove that the farthest point mapping has period 2. Elaborating on the analogy with Geometry, we study graphs satisfying Steinhaus' condition, i.e. graphs for which the farthest point mapping is single-valued and involutive.

We give an affirmative answer to an old conjecture proposed by Ludwig Danzer: there is a unique dissection of the square into five congruent convex tiles.

This paper was mentioned in an article on Martin Gardner's work, written by Colm Mulcahy for his Guest Blog in the Scientific American.

A graph G is almost hypohamiltonian if G is non-hamiltonian, there exists a vertex w such that G − w is non-hamiltonian, and for any vertex v ≠ w the graph G − v is hamiltonian. We prove the existence of an almost hypohamiltonian graph with 17 vertices and of a planar such graph with 39 vertices. Moreover, we find a 4-connected almost hypohamiltonian graph, while Thomassen's question whether 4-connected hypohamiltonian graphs exist remains open. We construct planar almost hypohamiltonian graphs of order n for every n ≥ 74. During our investigation we draw connections between hypotraceable, hypohamiltonian and almost hypohamiltonian graphs, and discuss a natural extension of almost hypohamiltonicity. Finally, we give a short argument disproving a conjecture of Chvátal (originally disproved by Thomassen), strengthen a result of Araya and Wiener on cubic planar hypohamiltonian graphs, and mention open problems.

Motivated by the computational complexity of determining whether a graph is hamiltonian, we study under algorithmic aspects a class of polyhedra called k-pyramids, introduced in [C. T. Zamfirescu and T. I. Zamfirescu, Math. Nachr. 284 (2011) 1739–47], and discuss related applications. We prove that determining whether a given graph is the 1-skeleton of a k-pyramid, and if so whether it is belted or not, can be done in polynomial time for k ≤ 3. The impact on hamiltonicity follows from the traceability of all 2-pyramids and non-belted 3-pyramids, and from the hamiltonicity of all non-belted 2-pyramids. The algorithm can also be used to determine the outcome for larger values of k, but the complexity increases with k. Lastly, we present applications of the algorithm, and improve the known bounds for the minimal cardinality of systems of bases called foundations in graph families with interesting properties concerning traceability and hamiltonicity.

No hypohamiltonian graphs are embeddable in the planar square lattice L². The lattice L² contains, however, graphs in which every vertex is missed by some longest cycle. In this paper we present graphs with this property, embeddable in various lattices, and of considerably smaller order than those previously known.

We present a novel method of constructing non-obtuse and acute triangulations of planar convex n-gons, improving existing bounds presented in [L. Yuan, Discrete Comput. Geom. 34 (2005) 697–706] for 6 ≤ n ≤ 11 and 6 ≤ n ≤ 56, respectively.

Motivated by applications in numerical analysis, we investigate balanced triangulations, i.e. triangulations where all angles are strictly larger than π/6 and strictly smaller than π/2, giving the optimal lower bound for the number of triangles in the case of the square. We also investigate platonic surfaces, where we find for each one its respective optimal bound. In particular, we settle (affirmatively) the open question whether there exist acute triangulations of the regular dodecahedral surface with 12 acute triangles [J. Itoh and T. Zamfirescu, Eur. J. Combin. 28 (2007) 1072–86].

This is a survey of results obtained during the last 45 years regarding the intersection behaviour of all longest paths, or all longest cycles, in connected graphs. Planar graphs and graphs of higher connectivity receive special attention. Graphs embeddable in the cubic lattice of arbitrary dimension, and graphs embeddable in the triangular or hexagonal lattice of the plane are also discussed. Results concerning the case when not all, but just some longest paths or cycles are intersected, for example two or three of them, are also reported.

We introduce the class of (2)-pancyclic graphs, which are simple undirected finite connected graphs of order n having exactly two cycles of length p for each p satisfying 3 ≤ p ≤ n, analyze their properties, and give several examples of such graphs, among which are the smallest.

We give a brief introduction to the topic of two-dimensional acute triangulations, mention results on related areas, survey existing achievements—with emphasis on recent activity—and list related open problems, both concrete and conceptual.

We prove that for every k ≥ 0 there is an n₀(k) such that, for every n ≥ n₀, there exists a hypohamiltonian graph which has order n and crossing number k.

We investigate here the hamiltonicity of a class of polytopes generalizing pyramids, prisms, and polytopes with Halin 1-skeleta.

We answer an open question on planar non-hamiltonian bihomogeneously traceable digraphs without opposite arcs by constructing an infinite family of such graphs.

Motivated by various applications triangulations of surfaces using only acute triangles have been recently studied. Triangles and quadrilaterals can be triangulated with at most 7, respectively 10, acute triangles. Doubly covered triangles can be triangulated with at most 12 acute triangles. In this paper we investigate the acute triangulations of doubly covered convex quadrilaterals, and show that they can be triangulated with at most 20 acute triangles.

We present a planar hypohamiltonian graph on 48 vertices, and derive some consequences.

In Petersen's well-known cubic graph every vertex is missed by some longest cycle. Thomassen produced a planar graph with this property. Grünbaum found a cubic graph, in which any two vertices are missed by some longest cycle. In this paper we present a cubic planar graph fulfilling this condition.

We prove that every doubly covered triangle can be triangulated with 12 acute triangles, and this number is best possible.