IF  AIS Carol T. Zamfirescu
Carol T. Zamfirescu
Dipl.-Math. (TU Dortmund), Ph.D. (UGent)

Tricube Main Page · Updated on 11 January 2024 · Contact: czamfirescu@gmail.com


News

• Our paper “Few hamiltonian cycles in graphs with one or two vertex degrees” (joint work with J. Goedgebeur, J. Jooken, O. S. Lo, and B. Seamone) has been accepted for publication in the journal Mathematics of Computation; see article № 60 below.
• The article “K2-hamiltonian graphs: II” (joint work with J. Goedgebeur, J. Renders, and G. Wiener) has been accepted for publication in the Journal of Graph Theory; see article № 58 below.
• My paper “On a conjecture of Grünbaum on longest cycles” has been accepted for publication in the European Journal of Combinatorics; see article № 56 below.
• On 1 January 2023, I have begun a 3-year term as member of the FWO (Research Foundation Flanders) W&T1 Fellowship panel on Mathematical Sciences. This panel judges all applications for PhD and postdoctoral fellowships in the Mathematical Sciences submitted to the FWO.


Publications
  Google Scholar h-index: 11        Erdős number: 2

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


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


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


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


64. Generation and a new infinite family of K2-hypohamiltonian graphs (with J. Goedgebeur and J. Renders)
Submitted.
      Abstract
We present an algorithm which can generate all pairwise non-isomorphic K2-hypohamiltonian graphs, i.e. non-hamiltonian graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph, of a given order. We introduce new bounding criteria especially designed for K2-hypohamiltonian graphs. Using this algorithm, we improve upon earlier computational results. More specifically, we characterise the orders for which K2-hypohamiltonian graphs exist and improve existing lower bounds on the orders of the smallest planar and the smallest bipartite K2-hypohamiltonian graphs. Furthermore, motivated by a theorem of Thomassen on hypohamiltonian graphs, we show that there exist K2-hypohamiltonian graphs with large maximum degree and size.
      Links
arXiv:2311.10593


63. Counting cycles in planar triangulations (with O. S. Lo)
Submitted.
      Abstract
We investigate the minimum number of cycles of specified lengths in planar n-vertex triangulations G. It is proven that this number is Ω(n) for any cycle length at most 3 + max { rad(G*), ((n − 3)/2)log32 }, where rad(G*) denotes the radius of the triangulation's dual, which is at least logarithmic but can be linear in the order of the triangulation. We also show that there exist planar hamiltonian n-vertex triangulations containing O(n) many k-cycles for any k ∈ { nn5, ..., n }. Furthermore, we prove that planar 4-connected n-vertex triangulations contain Ω(n) many k-cycles for every k ∈ { 3, ..., n }, and that, under certain additional conditions, they contain Ω(n2) k-cycles for many values of k, including n.
      Links
arXiv:2210.01190


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


61. Shortness parameters of polyhedral graphs with few distinct vertex degrees (with O. S. Lo, J. M. Schmidt, and N. Van Cleemput)
Submitted.
      Abstract
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.


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


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


58. K2-hamiltonian graphs: II (with J. Goedgebeur, J. Renders, and G. Wiener)
To appear in: Journal of Graph Theory.
      Abstract
In this paper we use theoretical and computational tools to continue our investigation of K2-hamiltonian graphs, i.e. graphs in which the removal of any pair of adjacent vertices yields a hamiltonian graph, and their interplay with K1-hamiltonian graphs, i.e. graphs in which every vertex-deleted subgraph is hamiltonian. Perhaps surprisingly, there exist graphs that are both K1- and K2-hamiltonian, yet non-hamiltonian, e.g. the Petersen graph. Grünbaum conjectured that every planar K1-hamiltonian graph must itself be hamiltonian; Thomassen disproved this conjecture. Here we show that even planar graphs that are both K1- and K2-hamiltonian need not be hamiltonian, and that the number of such graphs grows at least exponentially. Motivated by results of Aldred, McKay, and Wormald, we determine for every integer n that is not 14 or 17 whether there exists a K2-hypohamiltonian, i.e. non-hamiltonian and K2-hamiltonian, graph of order n, and characterise all orders for which such cubic graphs and such snarks exist. We also describe the smallest cubic planar graph which is K2-hypohamiltonian, as well as the smallest planar K2-hypohamiltonian graph of girth 5. We conclude with open problems and by correcting two inaccuracies from the first article [Zamfirescu, SIAM J. Disc. Math. 35 (2021) 1706–28].
      Links
arXiv:2311.05262    DOI: 10.1002/jgt.23057


57. On non-hamiltonian polyhedra without cubic vertices and their vertex-deleted subgraphs (with J. Goedgebeur and T. Gringore)
To appear in: Discussiones Mathematicae Graph Theory.
      Abstract
Thomassen proved in 1978 that if in an n-vertex planar graph G whose minimum degree is at least 4 all vertex-deleted subgraphs of G are hamiltonian, then G is hamiltonian. It was recently shown that in the preceding sentence, “all” can be replaced by “at least n − 5”. In this note we prove that, if 3-connectedness is assumed, it cannot be replaced by n − 24 (or any other integer greater than 24). The exact threshold remains unknown. We show that the same conclusion holds for triangulations and use computational means to prove that, under a natural restriction, this result is best possible.
      Links
DOI: 10.7151/dmgt.2514


56. On a conjecture of Grünbaum on longest cycles
Europ. J. Combin. 114 (2023) Article 103791.
      Abstract
Grünbaum conjectured that for any integer k ≥ 2, there exists no n-vertex graph G of circumference n − k in which the removal of any k vertices from G yields a hamiltonian graph. We show that for any positive integers c and k there is an infinite family of c-connected graphs of circumference k less than their order, in which the limit (as the graphs' order tends to infinity) of the ratio between the number of k-vertex sets whose removal yields a hamiltonian graph and the number of all k-vertex sets is 1. Motivated by a question of Katona, Kostochka, Pach, and Stechkin, it is proven that there exists an infinite family of non-hamiltonian graphs of increasing diameter d in which the removal of any two vertices at distance 1 or any distance at least (d + 6)/2 yields a hamiltonian graph.
      Links
Full text as PDF    DOI: 10.1016/j.ejc.2023.103791


55. On the hamiltonicity of a planar graph and its vertex-deleted subgraphs
J. Graph Theory 102, Iss. 1 (2023) 180–93.
      Abstract
Tutte proved that every planar 4-connected graph is hamiltonian. Thomassen showed that the same conclusion holds for the superclass of planar graphs with minimum degree at least 4 in which all vertex-deleted subgraphs are hamiltonian. We here prove that if in a planar n-vertex graph with minimum degree at least 4 at least n − 5 vertex-deleted subgraphs are hamiltonian, then the graph contains two hamiltonian cycles, but that for every c < 1 there exists a non-hamiltonian polyhedral n-vertex graph with minimum degree at least 4 containing c n hamiltonian vertex-deleted subgraphs. Furthermore, we study the hamiltonicity of planar triangulations and their vertex-deleted subgraphs as well as Bondy's meta-conjecture, and prove that a polyhedral graph with minimum degree at least 4 in which all vertex-deleted subgraphs are traceable, must itself be traceable.
      Links
Full text as PDF    DOI: 10.1002/jgt.22864


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


53. The Connectivity of the Dual (with D. Bokal and G. Brinkmann)
J. Graph Theory 101, Iss. 2 (2022) 182–209.
      Abstract
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.
      Links
arXiv:1812.08510    DOI: 10.1002/jgt.22819


52. On 2-factors splitting an embedded graph into two plane graphs (with G. Brinkmann and S. Chiers)
Graphs Combin. 38 (2022) Article number: 76.
      Abstract
We investigate 2-planarizing 2-factors, i.e. 2-factors of embedded graphs so that cutting along the cycles of the 2-factor we get two plane graphs where the cycles of the 2-factors are a spanning set of face boundaries in each of the graphs. We will give necessary criteria for an abstract graph to have an embedding with a 2-planarizing 2-factor as well as necessary criteria for embedded graphs to have such a 2-factor. Along the way, we discuss to which degree classical results from planar hamiltonicity theory can be extended in our framework. In addition we present computational results on how common 2-planarizing 2-factors are in small cubic graphs.
      Links
Full text as PDF    DOI: 10.1007/s00373-022-02473-3


51. Regular graphs with few longest cycles
SIAM J. Discrete Math. 36, Iss. 1 (2022) 755–76.
      Abstract
Motivated by work of Haythorpe, Thomassen and the author showed that there exists a positive constant c such that there is an infinite family of 4-regular 4-connected graphs, each containing exactly c hamiltonian cycles. We complement this by proving that the same conclusion holds for planar 4-regular 3-connected graphs, although it does not hold for planar 4-regular 4-connected graphs by a result of Brinkmann and Van Cleemput, and that it holds for 4-regular graphs of connectivity 2 with the constant 144 < c, which we believe to be minimal among all hamiltonian 4-regular graphs of sufficiently large order. We then disprove a conjecture of Haythorpe by showing that for every non-negative integer k there is a 5-regular graph on 26 + 6k vertices with 2k+3 · 3k+10 hamiltonian cycles. We prove that for every d ≥ 3 there is an infinite family of hamiltonian 3-connected graphs with minimum degree d, with a bounded number of hamiltonian cycles. It is shown that if a 3-regular graph G has a unique longest cycle C, at least two components of GE(C) have an odd number of vertices on C, and that there exist 3-regular graphs with exactly two such components.
      Remarks
On page 766, at the beginning of Section 3, instead of referring to Table 1 one must refer to Table 3 from [J. Goedgebeur, B. Meersman, and C. T. Zamfirescu, Graphs with few Hamiltonian cycles, Math. Comp. 89 (2020) 965–991].
      Links
arXiv:2104.10020    DOI: 10.1137/21M1414048


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


49. Counterexamples to a conjecture of Merker on 3-connected cubic planar graphs with a large cycle spectrum gap
Discrete Math. 345, Iss. 6 (2022) 112824.
      Abstract
Merker conjectured that if k ≥ 2 is an integer and G a 3-connected cubic planar graph of circumference at least k, then the set of cycle lengths of G must contain at least one element of the interval [k, 2k+2]. We here prove that for every even integer k ≥ 6 there is an infinite family of counterexamples.
      Links
arXiv:2009.00423    DOI: 10.1016/j.disc.2022.112824


48. Planar Hypohamiltonian Oriented Graphs (with A. P. Burger, J. P. de Wet, M. Frick, and N. Van Cleemput)
J. Graph Theory 100, Iss. 1 (2022) 50–68.
      Abstract
In 1978 Thomassen asked whether planar hypohamiltonian oriented graphs exist. Infinite families of such graphs have since been described but for infinitely many n it remained an open question whether planar hypohamiltonian oriented graphs of order n exist. In this paper we develop new methods for constructing hypohamiltonian digraphs, which, combined with efficient graph generation algorithms, enable us to fully characterise the orders for which planar hypohamiltonian oriented graphs exist. Our novel methods also led us to discover the planar hypohamiltonian oriented graph of smallest order and size, as well as infinitely many hypohamiltonian orientations of maximal planar graphs. Furthermore, we answer a question related to a problem of Schiermeyer on vertex degrees in hypohamiltonian oriented graphs, and characterise all the orders for which planar hypotraceable oriented graphs exist.
      Links
Full text as PDF    DOI: 10.1002/jgt.22765


47. Vertex degrees and 2-cuts in graphs with many hamiltonian vertex-deleted subgraphs
Inform. Proc. Lett. 174 (2022) Article 106192.
      Abstract
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 k0 such that for every kk0 infinitely many planar k-graphs of connectivity 2 and minimum degree 4 exist. As a variation of a result of Thomassen, we show that certain planar 3-graphs must contain a cubic vertex.
      Links
Full text as PDF    DOI: 10.1016/j.ipl.2021.106192


46. 4-regular 4-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles (with C. Thomassen)
Australasian J. Combin. 81, Iss. 2 (2021) 334–8.
      Abstract
We prove that there exists an infinite family of 4-regular 4-connected Hamiltonian graphs with a bounded number of Hamiltonian cycles. We do not know if there exists such a family of 5-regular 5-connected Hamiltonian graphs.
      Links
Full text as PDF    Journal Link


45. K2-hamiltonian graphs: I
SIAM J. Discrete Math. 35, Iss. 3 (2021) 1706–28.
      Abstract
Motivated by a conjecture of Grünbaum and a problem of Katona, Kostochka, Pach, and Stechkin, both dealing with non-hamiltonian n-vertex graphs and their (n − 2)-cycles, we investigate K2-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 K2-hamiltonian graphs, both of the 3-edge-colourable and the non-3-edge-colourable variety. In fact, cubic K2-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 K2-hamiltonian graphs of any maximum degree exist. Several operations conserving K2-hamiltonicity are described, one of which leads to the result that there exists an infinite family of non-hamiltonian K2-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 K2-hamiltonian graph with minimum degree at least 4 is hamiltonian. Finally, we investigate K2-traceable graphs, and discuss open problems.
      Remarks
Proposition 6 in Section 3.2 discusses the so-called dot product in the context of K2-hamiltonicity. Unfortunately, the third and fourth paragraphs of its “proof” contain errors. Corrections have been added in Section 4 of the second paper in this series, see article № 58. A minor issue with Lemma 3 in Section 3.1 is also corrected.
      Links
Full text as PDF    DOI: 10.1137/20M1355252


44. On 3-polytopes with non-hamiltonian prisms (with D. Ikegami and S. Maezawa)
J. Graph Theory 97, Iss. 4 (2021) 569–77.
      Abstract
Š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.
      Links
Full text as PDF    DOI: 10.1002/jgt.22672


43. Non-hamiltonian graphs in which every edge-contracted subgraph is hamiltonian (with I. Fabrici, T. Madaras, M. Timková, and N. Van Cleemput)
Appl. Math. Comput. 392 (2021) Article 125714.
      Abstract
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.
      Links
Full text as PDF    Zbl 1462.05206    MR 4164893    DOI: 10.1016/j.amc.2020.125714


42. Spiders everywhere (with G. Wiener and M. Yokota)
Discrete Appl. Math. 289 (2021) 516–22.
      Abstract
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.
      Links
Full text as PDF    Zbl 1454.05068    MR 4184344    DOI: 10.1016/j.dam.2020.11.017


41. Long Cycles and Spanning Subgraphs of Locally Maximal 1-planar Graphs (with I. Fabrici, J. Harant, T. Madaras, S. Mohr, and R. Soták)
J. Graph Theory 95, Iss. 1 (2020) 125–37.
      Abstract
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.
      Links
arXiv:1912.08028    MR 4130388    DOI: 10.1002/jgt.22542


40. Non-hamiltonian 1-tough triangulations with disjoint separating triangles (with J. Fujisawa)
Discrete Appl. Math. 284 (2020) 622–5.
      Abstract
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.
      Links
Full text as PDF    Zbl 1443.05108    MR 4115510    DOI: 10.1016/j.dam.2020.03.053


39. On minimum leaf spanning trees and a criticality notion (with K. Ozeki and G. Wiener)
Discrete Math. 343, Iss. 7 (2020) Article 111884.
      Abstract
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.
      Links
Full text as PDF    Zbl 1440.05062    MR 4076879    DOI: 10.1016/j.disc.2020.111884


38. Structural and computational results on platypus graphs (with J. Goedgebeur and A. Neyt)
Appl. Math. Comput. 386 (2020) Article 125491.
      Abstract
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].
      Links
arXiv:1712.05158    Zbl 1462.05110    MR 4119967    DOI: 10.1016/j.amc.2020.125491


37. Shortness Coefficient of Cyclically 4-Edge-Connected Cubic Graphs (with O. S. Lo, J. M. Schmidt, and N. Van Cleemput)
Electron. J. Combin. 27, Iss. 1 (2020) Article Number P1.43.
      Abstract
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.
      Links
Full text as PDF    Zbl 1432.05059    MR 4064064    DOI: 10.37236/8440


36. Graphs with few Hamiltonian Cycles (with J. Goedgebeur and B. Meersman)
Math. Comp. 89 (2020) 965–91.
      Abstract
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.
      Links
arXiv:1812.05650    Zbl 1429.05114    MR 4044458    DOI: 10.1090/mcom/3465


35. On almost hypohamiltonian graphs (with J. Goedgebeur)
Discrete Math. Theoret. Comput. Sci. 21, No. 4 (2019) #5.
      Abstract
A graph G is almost hypohamiltonian (a.h.) if G is non-hamiltonian, there exists a vertex w in G such that G − w is non-hamiltonian, and G − v is hamiltonian for every vertex 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.
      Links
Full text as PDF    Zbl 1417.05114    MR 3995589    DOI: 10.23638/DMTCS-21-4-5


34. Polyhedra with few 3-cuts are hamiltonian (with G. Brinkmann)
Electron. J. Combin. 26, Iss. 1 (2019) Article Number P1.39.
      Abstract
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.
      Links
Full text as PDF    Zbl 1409.05122    MR 3934370    DOI: 10.37236/7771


33. On a question of van Aardt et al. on destroying all longest cycles
Graphs Combin. 35, Iss. 2 (2019) 479–83.
      Abstract
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.
      Links
Full text as PDF    Zbl 1409.05119    MR 3914971    DOI: 10.1007/s00373-019-02010-9


32. Cubic vertices in planar hypohamiltonian graphs
J. Graph Theory 90, Iss. 2 (2019) 189–207.
      Abstract
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.
      Links
Full text as PDF    Zbl 07363267    MR 3891935    DOI: 10.1002/jgt.22388


31. On the size of maximally non-hamiltonian digraphs (with N. Lichiardopol)
Ars Math. Contemp. 16, No. 1 (2019) 59–66.
      Abstract
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.
      Links
Full text as PDF    Zbl 1416.05166    MR 3904716    DOI: 10.26493/1855-3974.1291.ee9


30. Grinberg's Criterion (with G. Brinkmann)
Europ. J. Combin. 75 (2019) 32–42.
      Abstract
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.
      Links
Full text as PDF    Zbl 1400.05138    MR 3862952    DOI: 10.1016/j.ejc.2018.07.017


29. Every 4-Connected Graph with Crossing Number 2 is Hamiltonian (with K. Ozeki)
SIAM J. Discrete Math. 32, No. 4 (2018) 2783–94.
      Abstract
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.
      Links
Full text as PDF    Zbl 1401.05175    MR 3882945    DOI: 10.1137/17M1138443


28. Regular non-hamiltonian polyhedral graphs (with N. Van Cleemput)
Appl. Math. Comput. 338 (2018) 192–206.
      Abstract
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.
      Remarks
The main finding of this paper was mentioned in the September 2019 Feature Column of the American Mathematical Society, written by Joseph Malkevitch.
      Links
Full text as PDF    Zbl 1427.05126    MR 3843691    DOI: 10.1016/j.amc.2018.05.062


27. Hamiltonian properties of polyhedra with few 3-cuts—A survey (with K. Ozeki and N. Van Cleemput)
Discrete Math. 341, Iss. 9 (2018) 2646–60.
      Abstract
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.
      Remarks
On page 2647, entry J of the caption of Table 1 should be: Brinkmann and Zamfirescu (2019) [12]
      Links
Full text as PDF    Zbl 1392.05066    MR 3828776    DOI: 10.1016/j.disc.2018.06.015


26. Every graph occurs as an induced subgraph of some hypohamiltonian graph (with T. I. Zamfirescu)
J. Graph Theory 88, Iss. 4 (2018) 551–7.
      Abstract
We prove the titular statement. This settles a problem of Chvátal from 1973 and encompasses earlier results of Thomassen, who showed it for K3, 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.
      Links
Full text as PDF    Zbl 1393.05095    MR 3818596    DOI: 10.1002/jgt.22228


25. Gallai's question and constructions of almost hypotraceable graphs (with G. Wiener)
Discrete Appl. Math. 243 (2018) 270–8.
      Abstract
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 tG. 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 tG ≠ 0. In this article we study almost hypotraceable graphs, which constitute the extremal case tG = 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.
      Remarks
On page 271 it is stated that “We follow Chen et al. [4], and call a vertex present in all longest paths of a given graph a Gallai vertex, and the set of all Gallai vertices the Gallai set.” Although our definition of a Gallai vertex is indeed equivalent to the definition given in the aforementioned paper by Chen et al., our definition of a Gallai set is not. This does not change the validity of any of the given statements.
      Links
Full text as PDF    Zbl 1387.05072    MR 3804756    DOI: 10.1016/j.dam.2018.02.017


24. Non-hamiltonian triangulations with distant separating triangles (with K. Ozeki)
Discrete Math. 341, Iss. 7 (2018) 1900–2.
      Abstract
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.
      Links
Full text as PDF    Zbl 1387.05141    MR 3802143    DOI: 10.1016/j.disc.2018.03.018


23. Infinitely many planar cubic hypohamiltonian graphs of girth 5 (with J. Goedgebeur)
J. Graph Theory 88, Iss. 1 (2018) 40–5.
      Abstract
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.
      Links
Full text as PDF    Zbl 1391.05153    MR 3781602    DOI: 10.1002/jgt.22183


22. Congruent triangles in arrangements of lines
Ars Math. Contemp. 14, No. 2 (2018) 359–73.
      Abstract
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.
      Links
Full text as PDF    Zbl 1396.52022    MR 3812026    DOI: 10.26493/1855-3974.982.6d6


21. On hypohamiltonian snarks and a theorem of Fiorini (with J. Goedgebeur)
Ars Math. Contemp. 14, No. 2 (2018) 227–49.
      Abstract
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.
      Links
Full text as PDF    Zbl 1395.05044    MR 3812019    DOI: 10.26493/1855-3974.1176.9b7


20. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable
J. Graph Theory 86, Iss. 2 (2017) 223–43.
      Abstract
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.
      Remarks
Reference 11 from the journal version will not appear in Ars Math. Contemp. as indicated there—this is a misprint. Reference 11 has been split into articles № 23 and № 35, see above. In the proof of Theorem 2.3, “vV(S)” should be vS.
      Links
Full text as PDF    Zbl 1370.05115    MR 3684784    DOI: 10.1002/jgt.22122


19. Improved bounds for hypohamiltonian graphs (with J. Goedgebeur)
Ars Math. Contemp. 13, No. 2 (2017) 235–57.
      Abstract
A graph G is hypohamiltonian if G is non-hamiltonian and Gv is hamiltonian for every vV(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.
      Links
Full text as PDF    Zbl 1380.05034    MR 3720529    DOI: 10.26493/1855-3974.1044.eaa


18. Planar Hypohamiltonian Graphs on 40 Vertices (with M. Jooyandeh, B. D. McKay, P. R. J. Östergård, and V. H. Pettersson)
J. Graph Theory 84, Iss. 2 (2017) 121–33.
      Abstract
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.
      Links
Full text as PDF    Zbl 1356.05029    MR 3601121    DOI: 10.1002/jgt.22015


17. A cut locus for finite graphs and the farthest point mapping (with A. Maddaloni)
Discrete Math. 339, Iss. 1 (2016) 354–64.
      Abstract
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.
      Links
Full text as PDF    Zbl 1322.05048    MR 3404497    DOI: 10.1016/j.disc.2015.08.003


16. Dissecting the square into five congruent parts (with L. Yuan and T. I. Zamfirescu)
Discrete Math. 339, Iss. 1 (2016) 288–98.
      Abstract
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.
      Remarks
This paper was mentioned in an article on Martin Gardner's work, written by Colm Mulcahy for his Guest Blog in the Scientific American.
      Links
Full text as PDF    Zbl 1322.05038    MR 3404490    DOI: 10.1016/j.disc.2015.08.009


15. On Hypohamiltonian and Almost Hypohamiltonian Graphs
J. Graph Theory 79, Iss. 1 (2015) 63–81.
      Abstract
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.
      Remarks
The PDF available here contains corrections with respect to the published version. For details, see the last page of the PDF.
      Links
Full text as PDF    Zbl 1312.05076    MR 3322695    DOI: 10.1002/jgt.21815


14. Small k-pyramids and the complexity of determining k (with B. Schauerte)
J. Discrete Algorithms 30 (2015) 13–20.
      Abstract
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.
      Links
Full text as PDF    Zbl 06403388    MR 3305147    DOI: 10.1016/j.jda.2014.11.003   


13. Lattice graphs with non-concurrent longest cycles (with A. Dino Jumani and T. I. Zamfirescu)
Rend. Sem. Mat. Univ. Padova 132 (2014) 75–82.
      Abstract
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.
      Links
Full text as PDF    Zbl 1306.05114    MR 3276827    DOI: 10.4171/RSMUP/132-6


12. Improved bounds for acute triangulations of convex polygons
Util. Math. 91 (2013) 71–9.
      Abstract
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.
      Links
Full text as PDF    Zbl 1292.52003    MR 3097891


11. Balanced triangulations (with L. Jia, L. Yuan, and T. I. Zamfirescu)
Discrete Math. 313, Iss. 20 (2013) 2178–91.
      Abstract
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].
      Links
Full text as PDF    Zbl 1285.52004    MR 3084261    DOI: 10.1016/j.disc.2013.05.017


10. Intersecting longest paths and longest cycles: A survey (with A. Shabbir and T. I. Zamfirescu)
Electron. J. Graph Theory Appl. 1, No. 1 (2013) 56–76.
      Abstract
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.
      Links
Full text as PDF    Zbl 1306.05121    MR 3093252    DOI: 10.5614/ejgta.2013.1.1.6


09. (2)-pancyclic graphs
Discrete Appl. Math. 161, Iss. 7–8 (2013) 1128–36.
      Abstract
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.
      Remarks
For corrections with respect to the published version, please see: errata.
      Links
Full text as PDF    Zbl 1262.05090    MR 3030597    DOI: 10.1016/j.dam.2012.11.002


08. Survey of two-dimensional acute triangulations
Discrete Math. 313, Iss. 1 (2013) 35–49.
      Abstract
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.
      Links
Full text as PDF    Zbl 1261.52012    MR 3016971    DOI: 10.1016/j.disc.2012.09.016


07. Hypohamiltonian graphs and their crossing number
Electron. J. Combin. 19, Iss. 4 (2012) Article Number P12.
      Abstract
We prove that for every k ≥ 0 there is an n0(k) such that, for every nn0, there exists a hypohamiltonian graph which has order n and crossing number k.
      Remarks
For corrections with respect to the published version (which coincides with the PDF below), please see: errata.
      Links
Full text as PDF    Zbl 1266.05079    MR 3001649    DOI: 10.37236/2291


06. Hamiltonian properties of generalized pyramids (with T. I. Zamfirescu)
Math. Nachr. 281, Iss. 13 (2011) 1739–47.
      Abstract
We investigate here the hamiltonicity of a class of polytopes generalizing pyramids, prisms, and polytopes with Halin 1-skeleta.
      Links
Full text as PDF    Zbl 1236.05121    MR 2832679    DOI: 10.1002/mana.200910058


05. An infinite family of planar non-hamiltonian bihomogeneously traceable oriented graphs
Graphs Combin. 26, Iss. 1 (2010) 141–6.
      Abstract
We answer an open question on planar non-hamiltonian bihomogeneously traceable digraphs without opposite arcs by constructing an infinite family of such graphs.
      Links
Full text as PDF    Zbl 1231.05163    MR 2606625    DOI: 10.1007/s00373-010-0900-6


04. Acute triangulations of doubly covered convex quadrilaterals (with L. Yuan)
Boll. Unione Mat. Ital., Sez. B, Artic. Ric. Mat. (8) 10, Iss. 3 (2007) 933–8.
      Abstract
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.
      Links
Full text as PDF    Zbl 1185.52018    MR 2507906


03. A planar hypohamiltonian graph with 48 vertices (with T. I. Zamfirescu)
J. Graph Theory 55, Iss. 4 (2007) 338–42.      
      Abstract
We present a planar hypohamiltonian graph on 48 vertices, and derive some consequences.
      Remarks
Fig. 8 is incorrect: erratum.
      Links
Full text as PDF    Zbl 1120.05054    MR 2336805    DOI: 10.1002/jgt.20241


02. Regular graphs in which every pair of points is missed by some longest cycle (with B. Schauerte)
An. Univ. Craiova, Ser. Mat. Inf. 33 (2006) 154–73.
      Abstract
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.
      Remarks
On page 156, line 1, the cycle should be: a_1a_2a'_2a'_3a_3a_4a'_4a'_5a'_1a_1.
      Links
Full text as PDF    Zbl 1174.05419    MR 2359901    Journal Link


01. Acute triangulations of the double triangle
Bull. Math. Soc. Sci. Math. Roumanie 47 (95), Iss. 3–4 (2004) 189–93.
      Abstract
We prove that every doubly covered triangle can be triangulated with 12 acute triangles, and this number is best possible.
      Links
Full text as PDF    Zbl 1114.52012    MR 2121985    Journal Link


Talks
If you are interested in my slides, please e-mail me at: czamfirescu@gmail.com.

2023
On two conjectures of Grünbaum on longest cycles, held on December 13th at the Graph Theory Seminar organised by Jan Goedgebeur (KU Leuven Kulak, Belgium).
Spanning trees for many different numbers of leaves, held on November 21st at the Paderborn Graph Theory Online Seminar organised by Yulai Ma (Paderborn University, Germany; held online).
Spanning trees with many different numbers of leaves, held on November 17th in Dutch at the CAAGT Seminar (UGent, Belgium).
Edge-colorings, hamiltonian cycles, and a problem of Kotzig, invited 20-min. talk held on August 24th by video conference at the “Graph Coloring” minisymposium organised by Shun-ichi Maezawa at the 10th International Congress on Industrial and Applied Mathematics, Waseda University, Tokyo, Japan; held online.
On a conjecture of Grünbaum and K2-hypohamiltonian graphs, invited 25-min. talk held on July 19th by video conference at the Romanian Algorithms Days 2023, Roumania; held online.
Hamiltonian cycles and problems of Sheehan and Kotzig, held on January 23rd at a special session of the Maths Seminar at the Department of Mathematics, University of Delaware, Newark, DE, USA.
Recent progress on two cycle enumeration problems in graph theory, invited plenary talk held on January 9th at the NUMA Study Day 2023 (KU Leuven - Gent, Campus Rabot, Belgium).

2022
Missing cycle lengths in the cycle spectra of planar and toroidal graphs, held on November 28th at the Combinatorial Seminar organised by Shun-ichi Maezawa at Keio University, Tokyo, Japan; held online.
Counting cycles in regular and planar graphs, held on November 18th at the 39th Colloquium on Combinatorics (KolKom) (Paderborn University, Germany).
Counting cycles in regular and planar graphs, invited plenary talk held on September 9th by video conference at the 24th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG3) (Tokyo University of Science, Japan; held online).
Edge-colourings, hamiltonian cycles, and a problem of Kotzig, held on July 20th at the Discrete Mathematics Seminar organised by Ben Seamone at Dawson College, Montréal, Canada.
Hamiltonian cycles and 1-factors in 5-regular graphs, held on May 31st at the Combinatorics 2022 conference (Campus of Fondazione UniverMantova, Mantua, Italy).

2021
Counting cycles in regular and planar graphs, held on December 16th by video conference at the 43rd Australasian Combinatorics Conference (University of Melbourne, Australia; held online).
Counting cycles in regular and planar graphs, held on October 28th in Dutch at the CAAGT Seminar (UGent, Belgium).
Regular graphs with few longest cycles, held on July 12th by video conference at the Online Graph Theory Seminar organised by On-Hei Solomon Lo at Xiamen University, PR China; held online.
Hamiltonian cycles and 1-factors in 5-regular graphs, invited talk held on June 29th by video conference at the 5th Xi’an International Workshop on Graph Theory and Combinatorics (School of Mathematics and Statistics, Northwestern Polytechnical University, PR China; held online).
Counting hamiltonian cycles in regular graphs, held on June 2nd by video conference at the ILKE workshop, organised by Mária Maceková (Pavol Jozef Šafárik University in Košice, Slovakia) and Samuel Mohr (Masaryk University, Czech Republic). This online event replaces a workshop that should have taken place in Germany, but was held online.
K2-hamiltonian graphs, held on May 26th by video conference at CanaDAM 2021, Canada; held online.
On two conjectures of Grünbaum concerning longest cycles, held on May 17th by video conference at the Online Seminar on Graph Theory organised by S. Maezawa (University of Electro-Communications) and M. Furuya (Kitasato University), Japan; held online.
Grinberg's Criterion, held on April 19th by video conference at the Discrete Mathematics Seminars (Department of Computer Science, University of Verona, Italy; held online).

2020
Einblicke in die Graphentheorie: Hamiltonkreise in Polyedergraphen, talk held in German and accessible here (Youtube); recorded on November 18th and uploaded on November 21st on the occasion of the 25th anniversary of the German-language programme at Babeş-Bolyai University, Cluj-Napoca, Roumania; held online.
Mind the gap: Missing cycle lengths in the cycle spectra of polyhedral graphs, held on November 13th by video conference at the New York Combinatorics Seminar (CUNY, New York, NY, USA; held online).
Hamiltonian cycles and 1-factors in 5-regular graphs, held on July 9th by video conference at the Online Graph Theory Seminar organised by G. Mazzuoccolo and E. Steffen (hosted by Paderborn University, Germany; held online).
Hamiltonian cycles and 1-factors in 5-regular graphs, held on June 26th by video conference at the Graph Theory Seminar of Yokohama National University (YNU, Yokohama, Japan; held online).
Many quartic vertices and short longest cycles in prisms over 3-polytopes, held on March 26th by video conference at the Open Webinar (College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang, PR China; held online).
On 3-polytopes with non-hamiltonian prisms, held on March 13th in Dutch at the CAAGT Seminar (UGent, Belgium).

2019
Hamiltonian Properties of Planar Graphs and their Vertex-Deleted Subgraphs, held on November 15th (Department of Mathematics, Babeş-Bolyai University, Cluj-Napoca, Roumania).
Planar Hypohamiltonian Oriented Graphs, held on November 9th at the 38th Colloquium on Combinatorics (KolKom) (Paderborn University, Germany). On the occasion of this conference, a series of short videos was produced: Youtube Playlist.
Non-hamiltonian Regular Polyhedral Graphs, held on September 2nd (College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang, PR China).
On K1- and K2-hamiltonian graphs and two conjectures of Grünbaum, invited talk held on August 30th at the International Symposium on Discrete Geometry and Convexity (College of Mathematics and Information Science, Hebei Normal University, Shijiazhuang, PR China).
Hamiltonian Properties of Planar Graphs and their Vertex-Deleted Subgraphs, held on June 26th at the Doktorandenseminar of the Algorithms and Complexity Group (TU Wien, Austria).
Spiders Everywhere, held on May 28th at the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (University of Tokyo, Japan).
Grinberg's Criterion, held on May 24th at the Graph Theory Seminar of Yokohama National University (YNU, Yokohama, Japan).
Hamiltonian Properties of Planar Graphs and their Vertex-Deleted Subgraphs, held on May 3rd at the Graphes et Optimisation Seminar (LaBRI, Université de Bordeaux, France).
Graphs with few Hamiltonian Cycles, held on April 17th at the 10th Workshop on the Matthews-Sumner Conjecture and Related Problems (Hotel “Trend”, Plzeň, Czech Republic).
Planar Hypohamiltonian Oriented Graphs, held on March 29th in Dutch at the CAAGT Seminar (UGent, Belgium).
Hamiltonicity of planar graphs and their vertex-deleted subgraphs, held on March 5th at the 7th Ilmenau-Košice DAAD Research Workshop (Hotel “Jägerhof”, Königsee, Germany).

2018
Grinberg's Criterion, held on November 23rd at the 37th Colloquium on Combinatorics (KolKom) (Paderborn University, Germany).
Spanning subgraphs of planar graphs, invited plenary talk held on September 4th at the 27th Workshop on Cycles & Colourings (C&C) (Hotel “Atrium”, Nový Smokovec, Slovakia).
Longest Cycles in Polyhedral Graphs, held on May 29th at the Seminar of the Department of Computer Science and Information Theory (BME, Budapest, Hungary).
Spiders Everywhere!, held on May 18th in Dutch at the CAAGT Seminar (UGent, Belgium).
Cubic vertices in planar hypohamiltonian graphs, held on March 7th at the 49th Southeastern International Conference on Combinatorics, Graph Theory & Computing (FAU, Boca Raton, FL, USA).

2017
Grinberg's Criterion, held on December 18th in Dutch at the CAAGT Seminar (UGent, Belgium).
Every 4-connected graph with crossing number 2 is hamiltonian, held on September 4th at the 26th Workshop on Cycles & Colourings (C&C) (Hotel “Atrium”, Nový Smokovec, Slovakia).
Non-hamiltonian Polyhedra, held on June 26th at the Combinatorics Seminar of the Institute of Mathematics (Pavol Jozef Šafárik University, Košice, Slovakia).
Two Extensions of a Theorem of Tutte, held on May 25th at the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (ELTE, Budapest, Hungary).
Non-hamiltonian Regular Planar 3-Connected Graphs, held on May 18th in Dutch at the CAAGT Seminar (UGent, Belgium).
Hamiltonian Properties of Polyhedra, held on January 23rd at the Combinatorics Seminar of Keio University (Keio University, Tokyo, Japan).
Recent Results on Hypohamiltonian Graphs, held on January 21st at the Graph Theory Seminar of Tokyo University of Science (TUS, Tokyo, Japan).
Non-hamiltonian Polyhedra, held on January 19th at the Graph Theory Seminar of Yokohama National University (YNU, Yokohama, Japan).

2016
Strengthening a Theorem of Tutte on the Hamiltonicity of Polyhedra, held on November 10th at the 4th Bordeaux Graph Workshop (University of Bordeaux, France).
Planar Hypohamiltonian Graphs, held on November 4th at the 35th Colloquium on Combinatorics (KolKom) (Paderborn University, Germany).
Hypohamiltonian Graphs, held on May 30th at the Combinatorics Seminar of Keio University (Keio University, Tokyo, Japan).
Hamiltonian Properties of Polyhedra with Few 3-Cuts, held on May 25th at the Japanese Conference on Combinatorics and its Applications 2016 (Kyoto University, Japan).

2015
Platypuses, held on October 5th at the CAAGT Seminar (UGent, Belgium).
On non-hamiltonian graphs for which every vertex-deleted subgraph is traceable, held on September 7th at the 24th Workshop on Cycles & Colourings (C&C) (Hotel “Atrium”, Nový Smokovec, Slovakia).
A cut locus for finite graphs and the farthest point mapping, held on June 2nd at the 17th SEG Workshop (Hochschule Mittweida, Germany).
Hypohamiltonian and almost hypohamiltonian graphs, held on May 15th at the New York Combinatorics Seminar (CUNY, New York, NY, USA).
Hypohamiltonian and almost hypohamiltonian graphs, held on March 20th at the Fifth International Conference on Combinatorics, Graph Theory, and Applications (Hotel “Am Wald”, Elgersburg, Germany).
Hypohamiltonian and almost hypohamiltonian graphs, held on February 19th at the CAAGT Seminar (UGent, Belgium).

2014
Hypohamiltonian and almost hypohamiltonian graphs, held on November 27th at the 23rd Workshop '3in1' 2014 (AGH, Kraków, Poland).
Congruent triangles in line arrangements, held on June 24th at the 15th SEG Workshop (HTW Dresden, Germany).

2013
Hypohamiltonian and almost hypohamiltonian graphs, held on June 25th at the 13th SEG Workshop (Hochschule Mittweida, Germany).

2012
Acute Triangulations of Surfaces, held on July 4th at the International Conference on the Mathematics of Distances and Applications (Hotel “Panorama”, Saints Constantine and Helena, Bulgaria).
Many hamiltonian paths in non-hamiltonian digraphs, held on June 12th in German at the 11th SEG Workshop (HTW Dresden, Germany).
Planar hypohamiltonian graphs, held on June 1st at the International Conference on Cycles in Graphs in conjunction with the 27th Annual Shanks Lectures (VU, Nashville, TN, USA).
Planar hypohamiltonian graphs, held on May 22nd (UGent, Belgium).
Hamiltonian Properties of Generalized Pyramids, held on January 24th in German at the 10th SEG Workshop (Math. Dept. TU Chemnitz, Germany).

2011
Hamiltonian Properties of Generalized Pyramids, held on November 24th at the 20th Workshop '3in1' 2011 (Hotel “Prezydent”, Krynica, Poland).
Planar hypohamiltonian graphs, held on October 22nd at the 5th International Conference on Research and Education in Mathematics (ICREM) (ITB, Bandung, Indonesia).
Planar hypohamiltonian graphs, held on September 5th at the 20th Workshop on Cycles & Colourings (C&C) (Hotel “Atrium”, Nový Smokovec, Slovakia).
(2)-pancyclic graphs and planar hypohamiltonian graphs, held on August 16th (Hebei Normal University, Shijiazhuang, PR China).
(2)-pancyclic graphs, held on July 13th at the 4th International Workshop on Optimal Network Topologies (IWONT) (ULB, Brussels, Belgium).
Planar hypohamiltonian graphs, held on June 28th in German at the 9th SEG Workshop (CS Dept. TU Chemnitz, Germany).
Sur les bicyclettes, held on May 20th in French (LMIA, Mulhouse, France).
(2)-pancyclic graphs, held on April 10th at the DIMAP Workshop on Combinatorics and Graph Theory (DIMAP, University of Warwick, England).
Acute Triangulations of Surfaces, held on March 25th at the Fourth International Conference on Combinatorics, Graph Theory, and Applications (Hotel “Am Wald”, Elgersburg, Germany).

2010
Bihomogeneously Traceable Digraphs, held on November 22nd at the International Workshop Combinatorial and Computational Aspects of Optimization, Topology and Algebra (ACCOTA) 2010 (Hotel “Hacienda Real del Caribe”, Playa del Carmen, Mexico).
Hamiltonian Properties of Generalized Pyramids, held on November 12th at the 29th Colloquium on Combinatorics (KolKom) (MPII, Saarbrücken, Germany).
(2)-pancyclic graphs, held on September 9th at the 19th Workshop on Cycles & Colourings (C&C) (Hotel “Meander”, Tatranská Štrba, Slovakia).
Bihomogeneously Traceable Digraphs, held on July 2nd at the conference Combinatorics 2010 (Hotel “Il Chiostro”, Verbania, Italy).
Bihomogeneously Traceable Digraphs, held on March 13th at the Workshop on Hamiltonian Planar Graphs 2010 (ITB, Bandung, Indonesia).

2009
On Bihomogeneously Traceable Digraphs, held on November 27th at the 18th Workshop '3in1' 2009 (AGH, Kraków, Poland).
Acute Triangulations of Surfaces, held on March 25th in Roumanian (UB, Bucureşti, Roumania).

2008
Hamiltonian Properties of Generalized Pyramids, held on November 12th (LMIA, Mulhouse, France).


Teaching

Role Course Language   Institution Audience Semester
Lecturer Wiskunde: gevorderde technieken (Mathematics: Advanced Techniques) Dutch Ghent University, Belgium B.Sc. Chemistry,
M.Sc. Biomed. Sci.
2022/2023 (Spring)
Lecturer Planar graphs and hamiltonian cycles English University of Verona, Italy   M.Sc., Ph.D. Maths   2020/2021 (Spring)
Lecturer Algorithmische Graphentheorie (Algorithmic Graph Theory) German Babeș-Bolyai Univ., Roumania   B.Sc. CS 2019/2020–2021/2022 (Spring)
Lecturer Wiskunde: basisconcepten (Mathematics: Basic Concepts) Dutch Ghent University, Belgium B.Sc. Chemistry 2019/2020–2023/2024 (Fall)
Lecturer Wiskunde: algebra (Mathematics: Algebra) Dutch Ghent University, Belgium B.Sc. Chemistry 2017/2018–2018/2019 (Fall)
Assistant   Calculus (given by N. Van Cleemput) Dutch Ghent University, Belgium B.Sc. CS 2016/2017–2019/2020 (Spring)
Assistant Computerproject wiskunde (given by K. Coolsaet) Dutch Ghent University, Belgium B.Sc. Maths 2016/2017 (Fall)
Assistant Analyse I (given by N. Van Cleemput) Dutch Ghent University, Belgium B.Sc. CS 2015/2016 (Spring)


Conference Organisation

Upcoming and Current
• 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.

Past
Belgian Graph Theory Conference (organised together with J. Goedgebeur, D. Mattiolo, N. Van Cleemput, H. Van den Camp, and S. Van Overberghe), held at Ghent University, Belgium, on 9–11 August 2023.
Montreal Graph Theory Workshop (organised together with G. Hahn and B. Seamone), held at Dawson College, Montreal, Canada, on 29 May–2 June 2023.
Cycles in Planar Graphs (organised together with A. Shantanam), a contributed minisymposium within the Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM) 2021, Canada, held on 25 May 2021.
Ghent Graph Theory Workshop on Structure and Algorithms 2019 (organised together with J. Goedgebeur and N. Van Cleemput) held at Ghent University, Belgium, on 12–14 August 2019.
Bucharest Graph Theory Workshop on How to Span a Graph (organised together with R. Marinescu, C. Vîlcu, and T. Zamfirescu) held at the University of Bucharest, Roumania, on 15–17 August 2018.
Ghent Graph Theory Workshop on Structure and Algorithms 2017 (organised together with J. Goedgebeur and N. Van Cleemput) held at Ghent University, Belgium, on 16–18 August 2017.
Ghent Graph Theory Workshop on Longest Paths and Longest Cycles held at Ghent University, Belgium, on 1 and 2 August 2016.


Miscellanea
Euler is my academic great10-grandfather.

Dissertation
My Ph.D. Thesis entitled Hypohamiltonian and Almost Hypohamiltonian Graphs, supervised by Prof. Gunnar Brinkmann and defended on 10 May 2016 at Ghent University, is available here.


Students
PhD
• Since 5 July 2023, I am co-supervising (with the main supervisor being J. Goedgebeur, KU Leuven) the PhD thesis of Michiel Provoost.
For details, see this link.
• Since 15 September 2021, I am co-supervising (with the main supervisor being J. Goedgebeur, KU Leuven) the PhD thesis of Jarne Renders.
For details, see this link.
-
MSc
Andreas Awouters defended his Master's thesis “Homeomorfisch irreduceerbare opspannende bomen in planaire grafen” (Homeomorphically irreducible spanning trees of planar graphs) on 30 June 2023. Co-supervised with J. Goedgebeur.
Floor Van de Steene defended her Master's thesis “Het minimum bladgetal van grafen” (The minimum leaf number of graphs) on 2 September 2020. Co-supervised with J. Goedgebeur. Ms. Van de Steene is now at Comsof, Ghent, Belgium.
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 Verkorte Educatieve Masterproef titled “Een inbedding van topologische grafentheorie in het middelbaar onderwijs” (Embedding topological graph theory into high school education).
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.
-
Varia
Thomas Gringore did a 10-week research internship at Ghent University and defended his results on “Hamiltonian properties of planar graphs and their vertex-deleted graphs” on 26 August 2021. Co-supervised with J. Goedgebeur. Mr. Gringore is an engineering student at ENSTA Paris, France.


Jury Duties
• On 1 January 2023, I have begun a 3-year term as member of the FWO (Research Foundation Flanders) W&T1 Fellowship panel on Mathematical Sciences. This panel judges all applications for PhD and postdoctoral fellowships in the Mathematical Sciences submitted to the FWO.
• Member of the Examination Board of the Doctoral thesis “Local Symmetry Preserving Operations on Polyhedra” of Pieter Goetschalckx at Ghent University. Thesis defended on 28 August 2020.


Open Problems
Research Problems from the 18th Workshop '3in1' 2009 (ed.: M. Meszka)
Opuscula Math. 30, Iss. 4 (2010) 527–32.    Full text as PDF
Seven Problems on Hypohamiltonian and Almost Hypohamiltonian Graphs
Convexity and Discrete Geometry Including Graph Theory, Springer Proc. Math. & Stat. 148 (eds.: K. Adiprasito, I. Bárány, and C. Vîlcu) 253–5.    Full text as PDF


Refereeing
Applied Mathematics and Computation [certificate]
Ars Combinatoria
Australasian Journal of Combinatorics
Bulletin of the Belgian Mathematical Society - Simon Stevin
Discrete Applied Mathematics [certificate]
Discrete & Computational Geometry
Discrete Mathematics [certificate]
Discrete Mathematics & Theoretical Computer Science
Electronic Journal of Combinatorics
European Journal of Combinatorics
Graphs and Combinatorics
EATCS International Colloquium on Automata, Languages and Programming (ICALP)
IEEE Access
Information Processing Letters [certificate]
Journal of Algebra, Combinatorics, Discrete Structures, and Applications
Journal of Combinatorial Theory, Series B [certificate]
Journal of Graph Theory
Notices of the American Mathematical Society
SIAM Journal on Discrete Mathematics
Utilitas Mathematica
Proceedings of the Algorithms and Data Structures Symposium (WADS)

43 reviews for the American Mathematical Society's Mathematical Reviews.


Administration
Since 20 October 2020, I am the representative of postdocs and Ph.D. students in the council of the Department of Applied Mathematics, Computer Science and Statistics at Ghent University.


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


Visitors
since July 2014

               Flag Counter