Dipl.-Math. (TU Dortmund), Ph.D. (UGent)

Google Scholar h-index: 9 Erdős number: 2

51.

Submitted.

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, 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. The paper concludes with further results on edge-Kempe equivalence classes in planar 5-regular graphs.

arXiv:2008.03173

50.

Submitted.

Motivated by a conjecture of Grünbaum and a problem of Katona, Kostocha, Pach, and Stechkin, both dealing with non-hamiltonian *n*-vertex graphs and their (*n* − 2)-cycles, we investigate *K*_{2}-*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*_{2}-hamiltonian graphs, both of the 3-edge-colourable and the non-3-edge-colourable variety. In fact, cubic *K*_{2}-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*_{2}-hamiltonian graphs of any maximum degree exist. Several operations conserving *K*_{2}-hamiltonicity are described, one of which leads to the result that there exists an infinite family of non-hamiltonian *K*_{2}-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*_{2}-hamiltonian graph with minimum degree at least 4 is hamiltonian. By using an idea of Thomassen, we prove that planar non-hamiltonian *K*_{2}-hamiltonian graphs must contain at least four cubic vertices. Finally, we investigate *K*_{2}-traceable graphs, and discuss open
problems.

49.

Submitted.

Š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.

48.

Submitted.

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.

47.

Submitted.

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.

46.

Submitted.

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*_{0} such that for every *k* ≥ *k*_{0} 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 2- and 3-graphs without cubic vertices do not exist.

45.

Submitted.

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 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 related question by Schiermeyer on the minimum degree of planar hypohamiltonian oriented graphs, and characterise all the orders for which planar hypotraceable oriented graphs exist.

44.

Submitted.

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 in fact three hamiltonian cycles must be present, and 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. We then study the hamiltonicity of planar triangulations and their vertex-deleted subgraphs. Furthermore, in the light of Bondy’s meta-conjecture, we show that for any *k* there exists a polyhedral 4-regular graph in which all vertex-deleted subgraphs are hamiltonian, but whose cycle spectrum has a contiguous gap of size *k*. Finally, we prove that a polyhedral graph with minimum degree at least 4 in which all vertex-deleted subgraphs are traceable, must itself be traceable.

43.

Submitted.

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.

arXiv:1812.08510

42.

Submitted.

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.

41.

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].

arXiv:1712.05158 DOI: 10.1016/j.amc.2020.125491

40.

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.

Full text as PDF DOI: 10.1016/j.dam.2020.03.053

39.

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.

Full text as PDF DOI: 10.1016/j.disc.2020.111884

38.

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.

arXiv:1912.08028 DOI: 10.1002/jgt.22542

37.

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.

Full text as PDF Zbl 07165612 DOI: 10.37236/8440

36.

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.

arXiv:1812.05650 Zbl 1429.05114 MR 4044458 DOI: 10.1090/mcom/3465

35.

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.

Full text as PDF Zbl 1417.05114 MR 3995589 DOI: 10.23638/DMTCS-21-4-5

34.

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.

Full text as PDF Zbl 1409.05122 MR 3934370 DOI: 10.37236/7771

33.

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.

Full text as PDF Zbl 1409.05119 MR 3914971 DOI: 10.1007/s00373-019-02010-9

32.

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.

Full text as PDF MR 3891935 DOI: 10.1002/jgt.22388

31.

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.

Full text as PDF Zbl 1416.05166 MR 3904716 Journal Link

30.

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.

Full text as PDF Zbl 1400.05138 MR 3862952 DOI: 10.1016/j.ejc.2018.07.017

29.

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.

Full text as PDF Zbl 1401.05175 MR 3882945 DOI: 10.1137/17M1138443

28.

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.

Full text as PDF Zbl 1427.05126 MR 3843691 DOI: 10.1016/j.amc.2018.05.062

27.

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.

On page 2647, entry J of the caption of Table 1 should be: Brinkmann and Zamfirescu (2019) [12]

Full text as PDF Zbl 1392.05066 MR 3828776 DOI: 10.1016/j.disc.2018.06.015

26.

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*_{3}, 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.

Full text as PDF Zbl 1393.05095 MR 3818596 DOI: 10.1002/jgt.22228

25.

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.

Full text as PDF Zbl 1387.05072 MR 3804756 DOI: 10.1016/j.dam.2018.02.017

24.

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.

Full text as PDF Zbl 1387.05141 MR 3802143 DOI: 10.1016/j.disc.2018.03.018

23.

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.

Full text as PDF Zbl 1391.05153 MR 3781602 DOI: 10.1002/jgt.22183

22.

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.

Full text as PDF Zbl 1396.52022 MR 3812026 Journal Link

21.

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.

Full text as PDF Zbl 1395.05044 MR 3812019 Journal Link

20.

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.

Reference 11 from the journal version will not appear in

Full text as PDF Zbl 1370.05115 MR 3684784 DOI: 10.1002/jgt.22122

19.

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.

Full text as PDF MR 3720529 Journal Link

18.

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.

Full text as PDF Zbl 1356.05029 MR 3601121 DOI: 10.1002/jgt.22015

• I. Fabrici, T. Madaras, and M. Timková. Forbidden configurations for hypohamiltonian graphs,

• G. Wiener. New constructions of hypohamiltonian and hypotraceable graphs,

• B. D. McKay. Hypohamiltonian Planar Cubic Graphs with Girth 5,

• S. A. van Aardt, A. P. Burger, and M. Frick. The Existence of Planar Hypotraceable Oriented Graphs,

• G. Wiener. Leaf-Critical and Leaf-Stable Graphs,

• G. Wiener. On constructions of hypotraceable graphs,

• A. Shabbir and T. Zamfirescu. Gallai’s property for graphs in lattices on the torus and the Möbius strip,

17.

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.

Full text as PDF Zbl 1322.05048 MR 3404497 DOI: 10.1016/j.disc.2015.08.003

16.

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.

Full text as PDF Zbl 1322.05038 MR 3404490 DOI: 10.1016/j.disc.2015.08.009

15.

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.

The PDF available here contains corrections with respect to the published version. For details, see the last page of the PDF.

Full text as PDF Zbl 1312.05076 MR 3322695 DOI: 10.1002/jgt.21815

14.

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.

Full text as PDF Zbl 06403388 MR 3305147 DOI: 10.1016/j.jda.2014.11.003

13.

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.

Full text as PDF Zbl 1306.05114 MR 3276827 DOI: 10.4171/RSMUP/132-6

12.

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.

Full text as PDF Zbl 1292.52003 MR 3097891

11.

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].

Full text as PDF Zbl 1285.52004 MR 3084261 DOI: 10.1016/j.disc.2013.05.017

10.

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.

Full text as PDF Zbl 1306.05121 MR 3093252 DOI: 10.5614/ejgta.2013.1.1.6

• B. Li, L. Xiong, and J. Yin. Large degree vertices in longest cycles of graphs, II,

• G. Golan and S. Shan. Nonempty intersection of longest paths in 2

• J. Gutiérrez. Transversals of Longest Cycles in Chordal and Bounded Tree-Width Graphs,

• G. Chen, J. Ehrenmüller, C. G. Fernandes, C. G. Heise, S. Shan, P. Yang, and A. N. Yates. Nonempty intersection of longest paths in series-parallel graphs,

• A. S. Jobson, A. E. Kézdy, J. Lehel, and S. C. White. Detour trees,

• Y. Bashir, F. Nadeem, and A. Shabbir. Highly non-concurrent longest paths in lattices,

• F. Joos. A note on longest paths in circular arc graphs,

• F. Chen. Nonempty intersection of longest paths in a graph with a small matching number,

• A. Shabbir. Fault-tolerant designs in lattice networks on the Klein bottle,

• D. Rautenbach and J.-S. Sereni. Transversals of Longest Paths and Cycles,

09.

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.

For corrections with respect to the published version, please see: errata.

Full text as PDF Zbl 1262.05090 MR 3030597 DOI: 10.1016/j.dam.2012.11.002

• S. Liu. On r-(k)-pancyclic Graphs,

• C. Lai. On the size of graphs without repeated cycle lengths,

• A. Khodkar, O. Sawin, L. Mueller, and W. H. Choi. (r)-Pancyclic, (r)-Bipancyclic and Oddly (r)-Bipancyclic Graphs,

• S. Liu. Some extremal problems on the cycle length distribution of graphs,

• J. C. George, A. Khodkar, and W. D. Wallis. Pancyclic and Bipancyclic Graphs,

• M. Schaefer. The Graph Crossing Number and its Variants: A Survey,

08.

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.

Full text as PDF Zbl 1261.52012 MR 3016971 DOI: 10.1016/j.disc.2012.09.016

• D. Kröner and M. Rokyta. Error estimates for higher-order finite volume schemes for convection diffusion problems,

• S. Bau and S. M. Gagola III. Decomposition of closed orientable geometric surfaces into acute geodesic triangles,

• A. Joós. Finding equal-diameter tetrahedralizations of polyhedra,

• C. J. Bishop. Nonobtuse Triangulations of PSLGs,

• A. Bezdek and T. Bisztriczky. Finding equal-diameter triangulations in polygons,

• P. Zanaty and L. T. Dechevsky. On the Numerical Performance of FEM Based on Piecewise Rational Smooth Resolutions of Unity on Triangulations,

• S. Banerjee, B. B. Bhattacharya, S. Das, A. Karmakar, A. Maheshwari, and S. Roy. On the Construction of Generalized Voronoi Inverse of a Rectangular Tessellation,

07.

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

For corrections with respect to the published version (which coincides with the PDF below), please see: errata.

Full text as PDF Zbl 1266.05079 MR 3001649 DOI: 10.37236/2291

06.

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

Full text as PDF Zbl 1236.05121 MR 2832679 DOI: 10.1002/mana.200910058

05.

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

Full text as PDF Zbl 1231.05163 MR 2606625 DOI: 10.1007/s00373-010-0900-6

04.

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.

Full text as PDF Zbl 1185.52018 MR 2507906

• C. J. Bishop. Nonobtuse Triangulations of PSLGs,

• X. Feng, L. Yuan, and T. Zamfirescu. Acute Triangulations of Archimedean Surfaces. The Truncated Tetrahedron,

• X. Feng and L. Yuan. Acute Triangulations of the Cuboctahedral Surface,

• L. Yuan. Acute triangulations of trapezoids,

• J. Itoh and L. Yuan. Acute triangulations of flat tori,

• S. Marcus. Paradigme Universale III. Jocul (Roumanian). Editura Paralela 45, 2007, ISBN 978-973-47-0196-4. Cited on page 167.

• L. Yuan and T. Zamfirescu. Acute triangulations of flat Möbius strips,

03.

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

Fig. 8 is incorrect: erratum.

Full text as PDF Zbl 1120.05054 MR 2336805 DOI: 10.1002/jgt.20241

• I. Fabrici, T. Madaras, and M. Timková. Forbidden configurations for hypohamiltonian graphs,

• S. A. van Aardt, A. P. Burger, and M. Frick. The Existence of Planar Hypotraceable Oriented Graphs,

• F. Nadeem, A. Shabbir, and T. Zamfirescu. Planar Lattice Graphs with Gallai's Property,

• G. Wiener and M. Araya. On planar hypohamiltonian graphs,

• M. Araya and G. Wiener. On cubic planar hypohamiltonian and hypotraceable graphs,

02.

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.

On page 156, line 1, the cycle should be: a_1a_2a'_2a'_3a_3a_4a'_4a'_5a'_1a_1.

Full text as PDF Zbl 1174.05419 MR 2359901 Journal Link

01.

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

Full text as PDF Zbl 1114.52012 MR 2121985 Journal Link

• C. J. Bishop. Nonobtuse Triangulations of PSLGs,

• V. Pambuccian. Acute Triangulation of a Triangle in a General Setting,

• L. Yuan. Acute triangulations of trapezoids,

• J. Itoh and L. Yuan. Acute triangulations of flat tori,

• S. Marcus. Paradigme Universale III. Jocul (Roumanian). Editura Paralela 45, 2007, ISBN 978-973-47-0196-4. Cited on page 167.

• L. Yuan and T. Zamfirescu. Acute triangulations of flat Möbius strips,

• J. Itoh and T. Zamfirescu. Acute triangulations of the regular dodecahedral surface,

If you are interested in my slides, please e-mail me at:

○

○

•

•

•

♣

•

•

•

•

•

•

•

♣

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

Role | Course | Language | Institution | Audience | Semester |

Lecturer | Algorithmische Graphentheorie (Algorithmic Graph Theory) | German | Babeș-Bolyai Univ. | B.Sc. CS | 2019/2020 (Spring) |

Lecturer | Wiskunde: basisconcepten (Mathematics: Basic Concepts) | Dutch | Ghent University | B.Sc. Chemistry | 2019/2020 (Fall) |

Lecturer | Wiskunde: algebra (Mathematics: Algebra) | Dutch | Ghent University | B.Sc. Chemistry | 2017/2018 (Fall), 2018/2019 (Fall) |

T.A. | Calculus (given by N. Van Cleemput) | Dutch | Ghent University | B.Sc. CS | 2016/2017 (Spring), 2017/2018 (Spring), 2018/2019 (Spring), 2019/2020 (Spring) |

T.A. | Computerproject wiskunde (given by K. Coolsaet) | Dutch | Ghent University | B.Sc. Maths | 2016/2017 (Fall) |

T.A. | Analyse I (Analysis I, given by N. Van Cleemput) | Dutch | Ghent University | B.Sc. CS | 2015/2016 (Spring) |

Dissertation

My Ph.D. Thesis entitled

Students

• Sara Chiers defended her Master's thesis “Planariserende 2-factoren” (Planarising 2-factors) on 25 June 2020. Co-supervised with G. Brinkmann. Additionally, under my supervision, Ms. Chiers wrote a so-called

• Barbara Meersman defended her Master's thesis “Grafen met weinig hamiltoniaanse cykels” (Graphs with few hamiltonian cycles) on 26 January 2018. Co-supervised with J. Goedgebeur. Ms. Meersman is now at Be-Mobile, Melle, Belgium.

• Addie Neyt defended her Master's thesis “Platypus grafen: structuur en generatie” (Platypus graphs: structure and generation) on 23 June 2017. Co-supervised with J. Goedgebeur. Ms. Neyt is now at the Royal Military Academy, Brussels, Belgium.

Open Problems

•

•

Convexity and Discrete Geometry Including Graph Theory,

Conference Organisation

• Since 2017, organiser of the seminar of the combinatorial algorithms and algorithmic graph theory (CAAGT) research group at Ghent University. If you would like to give a talk, please send me an e-mail at czamfirescu@gmail.com.

•

•

•

•

Refereeing

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

26 reviews for the American Mathematical Society's

House of Graphs

A database of interesting graphs developed and maintained by G. Brinkmann, K. Coolsaet, J. Goedgebeur, and H. Mélot.

since July 2014