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

We—Jan Goedgebeur, Nico Van Cleemput, and I—are organising the Ghent Graph Theory Workshop 2019, to be held from 12 to 14 August at Ghent University. Speakers include Maria Chudnovsky (Princeton), Bill Jackson (Queen Mary University of London), Brendan McKay (Australian National University), and Bojan Mohar (Simon Fraser University and University of Ljubljana). For further information, please consult the website: http://www.ggtw.ugent.be/.

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.

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. We also show that 45/46 is an upper bound for the shortness coefficient of cyclically 4-edge-connected cubic graphs that are (i) planar with face lengths bounded above by some constant larger than 22, or (ii) of genus *g* for any prescribed *g* ≥ 0. Finally, for the shortness coefficient of general cyclically 4-edge-connected cubic graphs we prove a theorem that implies the recently given upper bound 7/8 of Máčajová and Mazák.

41.

Submitted.

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.

40.

Submitted.

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.

39.

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.

38.

Submitted.

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

37.

Submitted.

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.

36.

To appear in:

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

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 Journal Link

1. C. T. Zamfirescu. Cubic vertices in planar hypohamiltonian graphs,

1. C. T. Zamfirescu and T. I. Zamfirescu. Every graph occurs as an induced subgraph of some hypohamiltonian graph,

1. G. Wiener and C. T. Zamfirescu. Gallai's question and constructions of almost hypotraceable graphs,

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

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 Journal Link

2. G. Brinkmann, K. Ozeki, and N. Van Cleemput. Types of triangle in plane Hamiltonian triangulations and applications to domination and

1. K. Ozeki and C. T. Zamfirescu. Every 4-Connected Graph with Crossing Number 2 is Hamiltonian,

1. C. T. Zamfirescu. Cubic vertices in planar hypohamiltonian graphs,

1. A. Schmid and J. M. Schmidt. Computing Tutte Paths,

1. K. Ozeki, N. Van Cleemput, and C. T. Zamfirescu. Hamiltonian properties of polyhedra with few 3-cuts—A survey,

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 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 DOI: 10.1002/jgt.22388

1. J. Goedgebeur and C. T. Zamfirescu. On almost hypohamiltonian graphs,

1. K. Ozeki and C. T. Zamfirescu. Every 4-Connected Graph with Crossing Number 2 is Hamiltonian,

1. K. Ozeki, N. Van Cleemput, and C. T. Zamfirescu. Hamiltonian properties of polyhedra with few 3-cuts—A survey,

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

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 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 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 DOI: 10.1137/17M1138443

1. K. Ozeki, N. Van Cleemput, and C. T. Zamfirescu. Hamiltonian properties of polyhedra with few 3-cuts—A survey,

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.

Full text as PDF 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 (2018+) [12]

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

1. K. Ozeki and C. T. Zamfirescu. Every 4-Connected Graph with Crossing Number 2 is Hamiltonian,

1. N. Van Cleemput and C. T. Zamfirescu. Regular non-hamiltonian polyhedral graphs,

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 DOI: 10.1002/jgt.22228

1. J. Goedgebeur and C. T. Zamfirescu. On almost hypohamiltonian graphs,

1. C. T. Zamfirescu. On a question of van Aardt et al. on destroying all longest cycles,

1. C. T. Zamfirescu. Cubic vertices in planar hypohamiltonian graphs,

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

1. K. Ozeki, N. Van Cleemput, and C. T. Zamfirescu. Hamiltonian properties of polyhedra with few 3-cuts—A survey,

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

1. J. Goedgebeur and C. T. Zamfirescu. On Hypohamiltonian Snarks and a Theorem of Fiorini,

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 Journal Link

1. M. A. Fiol, G. Mazzuoccolo, and E. Steffen. Measures of edge-uncolorability of cubic graphs,

1. J. Goedgebeur and C. T. Zamfirescu. Infinitely many planar cubic hypohamiltonian graphs of girth 5,

1. C. T. Zamfirescu. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable,

20.

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

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

1. J. Goedgebeur and C. T. Zamfirescu. On almost hypohamiltonian graphs,

1. C. T. Zamfirescu. On a question of van Aardt et al. on destroying all longest cycles,

1. N. Lichiardopol and C. T. Zamfirescu. On the size of maximally non-hamiltonian digraphs,

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

1. J. Goedgebeur and C. T. Zamfirescu. On almost hypohamiltonian graphs,

1. C. T. Zamfirescu. Cubic vertices in planar hypohamiltonian graphs,

1. C. T. Zamfirescu and T. I. Zamfirescu. Every graph occurs as an induced subgraph of some hypohamiltonian graph,

1. G. Wiener and C. T. Zamfirescu. Gallai's question and constructions of almost hypotraceable graphs,

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

1. J. Goedgebeur and C. T. Zamfirescu. Infinitely many planar cubic hypohamiltonian graphs of girth 5,

1. J. Goedgebeur and C. T. Zamfirescu. On Hypohamiltonian Snarks and a Theorem of Fiorini,

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.

This paper is currently listed in Web of Science as *Highly Cited Paper*, i.e. top 1% in Mathematics.

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

7. J. Goedgebeur and C. T. Zamfirescu. On almost hypohamiltonian graphs,

7. C. T. Zamfirescu. Cubic vertices in planar hypohamiltonian graphs,

7. G. Brinkmann and C. T. Zamfirescu. Grinberg's Criterion,

7. C. T. Zamfirescu and T. I. Zamfirescu. Every graph occurs as an induced subgraph of some hypohamiltonian graph,

7. G. Wiener and C. T. Zamfirescu. Gallai's question and constructions of almost hypotraceable graphs,

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

6. J. Goedgebeur and C. T. Zamfirescu. Infinitely many planar cubic hypohamiltonian graphs of girth 5,

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

5. C. T. Zamfirescu. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable,

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

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

4. J. Goedgebeur and C. T. Zamfirescu. Improved bounds for hypohamiltonian graphs,

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

2. G. Wiener. On constructions of hypotraceable graphs,

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

3. C. T. Zamfirescu. On hypohamiltonian and almost hypohamiltonian graphs,

2. A. Shabbir, C. T. Zamfirescu, and T. Zamfirescu. Intersecting longest paths and longest cycles: A survey,

1. C. T. Zamfirescu. Hypohamiltonian graphs and their crossing number,

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

1. K. Xu, H. Liu, K. Ch. Das, and S. Klavžar. Embeddings into almost self-centered graphs of given radius,

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

3. J. Goedgebeur and C. T. Zamfirescu. On almost hypohamiltonian graphs,

3. C. T. Zamfirescu. Cubic vertices in planar hypohamiltonian graphs,

3. C. T. Zamfirescu and T. I. Zamfirescu. Every graph occurs as an induced subgraph of some hypohamiltonian graph,

3. G. Wiener and C. T. Zamfirescu. Gallai's question and constructions of almost hypotraceable graphs,

3. J. Goedgebeur and C. T. Zamfirescu. Infinitely many planar cubic hypohamiltonian graphs of girth 5,

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

2. C. T. Zamfirescu. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable,

2. J. Goedgebeur and C. T. Zamfirescu. Improved bounds for hypohamiltonian graphs,

2. V. Samodivkin. Hypo-efficient domination and hypo-unique domination,

1. G. Wiener. On constructions of hypotraceable graphs,

1. C. T. Zamfirescu. Hypohamiltonian graphs and their crossing number,

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

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

1. A. Shabbir, C. T. Zamfirescu, and T. Zamfirescu. Intersecting longest paths and longest cycles: A survey,

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

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

1. C. T. Zamfirescu. Survey of two-dimensional acute triangulations,

1. L. Yuan and T. Zamfirescu. Acute triangulations of double planar convex bodies,

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

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

1. C. T. Zamfirescu. Survey of two-dimensional acute triangulations,

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

1. J. Goedgebeur and C. T. Zamfirescu. On almost hypohamiltonian graphs,

1. C. T. Zamfirescu. On a question of van Aardt et al. on destroying all longest cycles,

9. C. T. Zamfirescu. Cubic vertices in planar hypohamiltonian graphs,

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

8. G. Wiener and C. T. Zamfirescu. Gallai's question and constructions of almost hypotraceable graphs,

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

7. C. T. Zamfirescu. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable,

7. M. Jooyandeh, B. D. McKay, P. R. J. Östergård, V. H. Pettersson, and C. T. Zamfirescu. Planar Hypohamiltonian Graphs on 40 Vertices,

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

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

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

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

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

1. A. Dino Jumani, C. T. Zamfirescu, and T. I. Zamfirescu. Lattice graphs with non-concurrent longest cycles,

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

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

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

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

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

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

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

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

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

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

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

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

06. L. Yuan. Acute Triangulations of Rectangles, with Angles Bounded Below, in: Convexity and Discrete Geometry Including Graph Theory,

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

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

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

02. 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,

01. L. Jia, L. Yuan, C. T. Zamfirescu, and T. I. Zamfirescu. Balanced triangulations,

01. L. Yuan and T. Zamfirescu. Acute triangulations of double planar convex bodies,

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 Journal Link

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

1. C. T. Zamfirescu. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable,

1. J. Goedgebeur and C. T. Zamfirescu. Improved bounds for hypohamiltonian graphs,

1. C. T. Zamfirescu. On hypohamiltonian and almost hypohamiltonian graphs,

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

2. A. Shabbir and T. Zamfirescu. Hamiltonicity in

1. B. Schauerte and C. T. Zamfirescu. Small

1. S. Malik, A. M. Qureshi, and T. Zamfirescu. Hamiltonicity of Cubic 3-Connected

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

1. N. Lichiardopol and C. T. Zamfirescu. On the size of maximally non-hamiltonian digraphs,

1. S. A. van Aardt, A. P. Burger, and M. Frick. An Infinite Family of Planar Hypohamiltonian Oriented Graphs,

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

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

09. L. Yuan. Acute Triangulations of Rectangles, with Angles Bounded Below, in: Convexity and Discrete Geometry Including Graph Theory,

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

07. C. T. Zamfirescu. Improved bounds for acute triangulations of convex polygons,

07. C. T. Zamfirescu. Survey of two-dimensional acute triangulations,

07. L. Yuan and T. Zamfirescu. Acute triangulations of double planar convex bodies,

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

05. L. Yuan. Acute Triangulations of Pentagons,

04. L. Yuan. Acute triangulations of trapezoids,

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

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

01. 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 erroneous: erratum.

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

5. C. T. Zamfirescu. Cubic vertices in planar hypohamiltonian graphs,

5. G. Wiener and C. T. Zamfirescu. Gallai's question and constructions of almost hypotraceable graphs,

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

5. C. T. Zamfirescu. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable,

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

3. J. Goedgebeur and C. T. Zamfirescu. Improved bounds for hypohamiltonian graphs,

3. M. Jooyandeh, B. D. McKay, P. R. J. Östergård, V. H. Pettersson, and C. T. Zamfirescu. Planar Hypohamiltonian Graphs on 40 Vertices,

3. C. T. Zamfirescu. On hypohamiltonian and almost hypohamiltonian graphs,

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

2. A. Shabbir, C. T. Zamfirescu, and T. Zamfirescu. Intersecting longest paths and longest cycles: A survey,

2. C. T. Zamfirescu. Hypohamiltonian graphs and their crossing number,

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

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

1. B. Schauerte and C. T. Zamfirescu. Regular graphs in which every pair of points is missed by some longest cycle,

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

1. A. Shabbir, C. T. Zamfirescu, and T. Zamfirescu. Intersecting longest paths and longest cycles: A survey,

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

1. C. T. Zamfirescu and T. I. Zamfirescu. A planar hypohamiltonian graph with 48 vertices,

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

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

11. L. Yuan. Acute Triangulations of Rectangles, with Angles Bounded Below, in: Convexity and Discrete Geometry Including Graph Theory,

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

09. C. T. Zamfirescu. Improved bounds for acute triangulations of convex polygons,

09. C. T. Zamfirescu. Survey of two-dimensional acute triangulations,

09. L. Yuan and T. Zamfirescu. Acute triangulations of double planar convex bodies,

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

07. L. Yuan. Acute Triangulations of Pentagons,

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

05. L. Yuan. Acute triangulations of trapezoids,

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

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

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

01. L. Yuan and C. T. Zamfirescu. Acute triangulations of doubly covered convex quadrilaterals,

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

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

•

•

•

•

•

•

♣

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

•

Dissertation

My Ph.D. Thesis entitled

Students

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

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

Open Problems

•

•

Convexity and Discrete Geometry Including Graph Theory,

Conference Organisation

• Co-organiser (together with J. Goedgebeur and N. Van Cleemput) of the

For more information, click here.

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

• Co-organiser (together with R. Marinescu, C. Vîlcu, and T. Zamfirescu) of the

For more information, click here.

• Co-organiser (together with J. Goedgebeur and N. Van Cleemput) of the

For more information, click here.

• Organiser of the

For more information, click here.

Refereeing

(20) Summaries for

Teaching in Dutch

Lecturer of the course “Wiskunde: algebra” | 2017/2018 (Fall), 2018/2019 (Fall) |

Teaching assistant for the course “Calculus” given by N. Van Cleemput | 2016/2017 (Spring), 2017/2018 (Spring), 2018/2019 (Spring) |

Teaching assistant for the course “Computerproject wiskunde” given by K. Coolsaet | 2016/2017 (Fall) |

Teaching assistant for the course “Analyse I” given by N. Van Cleemput | 2015/2016 (Spring) |

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