LINK Website of Carol T. Zamfirescu
Carol T. Zamfirescu
Dipl.-Math. (TU Dortmund), Ph.D. (UGent)

Tricube Main Page · Updated on 10 September 2018 · Contact: czamfirescu@gmail.com


Publications
Web of Science h-Index: 5         Erdős number: 2             

41. Shortness Coefficient of Cyclically 4-Edge-Connected Cubic Graphs (with O.-H. S. Lo, J. M. Schmidt, and N. Van Cleemput)
Submitted.
      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. 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.


40. Non-hamiltonian 1-tough triangulations with disjoint separating triangles (with J. Fujisawa)
Submitted.
      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.


39. Long Cycles and Spanning Subgraphs of Locally Maximal 1-planar Graphs (with I. Fabrici, J. Harant, T. Madaras, S. Mohr, and R. Soták)
Submitted.
      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.


38. Spiders Everywhere (with G. Wiener and M. Yokota)
Submitted.
      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.


37. Structural and computational results on platypus graphs (with J. Goedgebeur and A. Neyt)
Submitted.
      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


36. On minimum leaf spanning trees and a criticality notion (with K. Ozeki and G. Wiener)
Submitted.
      Abstract
In this article we address questions raised by Wiener concerning the minimum leaf number ml(G): If a graph G is hamiltonian or disconnected, we define ml(G) as 1 and ∞, respectively; otherwise let ml(G) be the number of leaves of a spanning tree of G with the fewest leaves among all spanning trees of G. A graph G with 2 ≤ ml(G) = ℓ < ∞ is called ℓ-leaf-critical if ml(G − v) = ℓ − 1 for every v ∈ V(G), and ℓ-leaf-stable if ml(G − v) = ℓ for every v ∈ V(G). We present new methods to construct leaf-stable and leaf-critical graphs, and improve bounds related to these families of graphs. These extend previous results of Horton, Thomassen, and Wiener.


35. On a question of van Aardt et al. on destroying all longest cycles
Submitted.
      Abstract
In 2015 van Aardt et al. [Discrete Appl. Math. 186 (2015) 251–9] asked whether for any k ∈ {10, 11, 13, 16} a 2-connected graph exists such that its circumference is k and the intersection of all of its cycles of length k is empty. We settle this question affirmatively for k ∈ {10, 13, 16}. For circumference 11, we present a 2-connected graph with the property that all but one vertex are avoided by some longest cycle.


34. On almost hypohamiltonian graphs (with J. Goedgebeur)
Submitted.
      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
See Section 3 of arXiv:1606.06577—this preprint has been split into articles № 23 and № 34.
      Cited by
1. C. T. Zamfirescu and T. I. Zamfirescu. Every graph occurs as an induced subgraph of some hypohamiltonian graph, J. Graph Theory 88, Iss. 4 (2018) 551–7. Cited on pages 551 and 552.
1. G. Wiener and C. T. Zamfirescu. Gallai's question and constructions of almost hypotraceable graphs, Discrete Appl. Math. 243 (2018) 270–8. Cited on pages 272, 275, and 276.
1. G. Wiener. New constructions of hypohamiltonian and hypotraceable graphs, J. Graph Theory 87, Iss. 4 (2018) 526–35. Cited on pages 526, 527, 529, 533, and 534.



33. Polyhedra with few 3-cuts are hamiltonian (with G. Brinkmann)
Submitted.
      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
arXiv:1606.01693
      Cited by
1. K. Ozeki, N. Van Cleemput, and C. T. Zamfirescu. Hamiltonian properties of polyhedra with few 3-cuts—A survey, Discrete Math. 341, Iss. 9 (2018) 2646–60. Cited on pages 2647, 2649, and 2651–3.


32. Every 4-connected graph with crossing number 2 is hamiltonian (with K. Ozeki)
To appear in: SIAM Journal on Discrete Mathematics.
      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.
      Cited by
1. K. Ozeki, N. Van Cleemput, and C. T. Zamfirescu. Hamiltonian properties of polyhedra with few 3-cuts—A survey, Discrete Math. 341, Iss. 9 (2018) 2646–60. Cited on page 2647.


31. Cubic vertices in planar hypohamiltonian graphs
To appear in: Journal of Graph Theory.
      Abstract
Using a result of Tutte, Thomassen showed in 1978 that every planar hypohamiltonian graph contains a cubic vertex. 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.
      Cited by
1. K. Ozeki, N. Van Cleemput, and C. T. Zamfirescu. Hamiltonian properties of polyhedra with few 3-cuts—A survey, Discrete Math. 341, Iss. 9 (2018) 2646–60. Cited on page 2651.
1. I. Fabrici, T. Madaras, and M. Timková. Forbidden configurations for hypohamiltonian graphs, Opuscula Math. 38, no. 3 (2018) 357–77. Cited on page 358.


30. Maximally non-hamiltonian graphs and digraphs (with N. Lichiardopol)
To appear in: Ars Mathematica Contemporanea.
      Abstract
A graph is called maximally non-hamiltonian if it is not hamiltonian, yet for any pair of non-adjacent vertices there exists a hamiltonian path connecting them—we call such graphs MNH. We present new results concerning MNH graphs, and extend the concept naturally to MNH digraphs, the size of which we bound from below and above, the upper bound being sharp.


29. 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    DOI: 10.1016/j.ejc.2018.07.017


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.
      Links
Full text as PDF    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 (2018+) [12]
      Links
Full text as PDF    DOI: 10.1016/j.disc.2018.06.015
      Cited by
1. N. Van Cleemput and C. T. Zamfirescu. Regular non-hamiltonian polyhedral graphs, Appl. Math. Comput. 338 (2018) 192–206. Cited on page 193.


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    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.
      Links
Full text as PDF    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    DOI: 10.1016/j.disc.2018.03.018
      Cited by
1. K. Ozeki, N. Van Cleemput, and C. T. Zamfirescu. Hamiltonian properties of polyhedra with few 3-cuts—A survey, Discrete Math. 341, Iss. 9 (2018) 2646–60. Cited on page 2655.


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    DOI: 10.1002/jgt.22183
      Cited by
1. J. Goedgebeur and C. T. Zamfirescu. On Hypohamiltonian Snarks and a Theorem of Fiorini, Ars Math. Contemp. 14, No. 2 (2018) 227–49. Cited on page 229.


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


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    Journal Link
      Cited by
1. J. Goedgebeur and C. T. Zamfirescu. Infinitely many planar cubic hypohamiltonian graphs of girth 5, J. Graph Theory 88, Iss. 1 (2018) 40–5. Cited on pages 40 and 42.
1. C. T. Zamfirescu. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable, J. Graph Theory 86, Iss. 2 (2017) 223–43. Cited on pages 224 and 230.


20. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable
J. Graph Theory 86, Iss. 2 (2017) 223–43.
      Links
Full text as PDF    Zbl 1370.05115    MR 3684784    DOI: 10.1002/jgt.22122
      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 № 34, see above.


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    MR 3720529    Journal Link
      Cited by
1. C. T. Zamfirescu and T. I. Zamfirescu. Every graph occurs as an induced subgraph of some hypohamiltonian graph, J. Graph Theory 88, Iss. 4 (2018) 551–7. Cited on pages 551 and 556.
1. G. Wiener and C. T. Zamfirescu. Gallai's question and constructions of almost hypotraceable graphs, Discrete Appl. Math. 243 (2018) 270–8. Cited on page 270.
1. I. Fabrici, T. Madaras, and M. Timková. Forbidden configurations for hypohamiltonian graphs, Opuscula Math. 38, no. 3 (2018) 357–77. Cited on page 358.
1. J. Goedgebeur and C. T. Zamfirescu. Infinitely many planar cubic hypohamiltonian graphs of girth 5, J. Graph Theory 88, Iss. 1 (2018) 40–5. Cited on pages 40 and 44.
1. J. Goedgebeur and C. T. Zamfirescu. On Hypohamiltonian Snarks and a Theorem of Fiorini, Ars Math. Contemp. 14, No. 2 (2018) 227–49. Cited on page 237.


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.
      Remarks
This paper is currently listed in Web of Science as Highly Cited Paper, i.e. top 1% in Mathematics.
      Links
Full text as PDF    Zbl 1356.05029    MR 3601121    DOI: 10.1002/jgt.22015
      Cited by
7. G. Brinkmann and C. T. Zamfirescu. Grinberg's Criterion, Europ. J. Combin. 75 (2019) 32–42. Cited on page 33.
7. C. T. Zamfirescu and T. I. Zamfirescu. Every graph occurs as an induced subgraph of some hypohamiltonian graph, J. Graph Theory 88, Iss. 4 (2018) 551–7. Cited on page 551.
7. G. Wiener and C. T. Zamfirescu. Gallai's question and constructions of almost hypotraceable graphs, Discrete Appl. Math. 243 (2018) 270–8. Cited on pages 270, 271, and 276.
7. I. Fabrici, T. Madaras, and M. Timková. Forbidden configurations for hypohamiltonian graphs, Opuscula Math. 38, no. 3 (2018) 357–77. Cited on page 357.
6. J. Goedgebeur and C. T. Zamfirescu. Infinitely many planar cubic hypohamiltonian graphs of girth 5, J. Graph Theory 88, Iss. 1 (2018) 40–5. Cited on page 40.
6. G. Wiener. New constructions of hypohamiltonian and hypotraceable graphs, J. Graph Theory 87, Iss. 4 (2018) 526–35. Cited on pages 526, 527, 529, 533, and 534.
5. C. T. Zamfirescu. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable, J. Graph Theory 86, Iss. 2 (2017) 223–43. Cited on pages 224, 238, and 241.
5. B. D. McKay. Hypohamiltonian Planar Cubic Graphs with Girth 5, J. Graph Theory 85, Iss. 1 (2017) 7–11. Cited on pages 7 and 8.
4. S. A. van Aardt, A. P. Burger, and M. Frick. The Existence of Planar Hypotraceable Oriented Graphs, Discrete Math. Theor. Comput. Sci. 19, No. 1 (2017) #4. Cited on page 2.
4. J. Goedgebeur and C. T. Zamfirescu. Improved bounds for hypohamiltonian graphs, Ars Math. Contemp. 13 (2017) 235–57. Cited on pages 236, 238, 248–50, and 254.
3. G. Wiener. Leaf-Critical and Leaf-Stable Graphs, J. Graph Theory 84, Iss. 4 (2017) 443–59. Cited on pages 445 and 458.
2. G. Wiener. On constructions of hypotraceable graphs, Electron. Notes Discrete Math. 54 (2016) 127–32. Cited on pages 127, 128, and 131.
1. A. Shabbir and T. Zamfirescu. Gallai’s property for graphs in lattices on the torus and the Möbius strip, Period. Math. Hung. 72, Iss. 1 (2016) 1–11. Cited on page 1.
3. C. T. Zamfirescu. On hypohamiltonian and almost hypohamiltonian graphs, J. Graph Theory 79, Iss. 1 (2015) 63–81. Cited on pages 64, 69, and 72–4.
2. A. Shabbir, C. T. Zamfirescu, and T. Zamfirescu. Intersecting longest paths and longest cycles: A survey, Electron. J. Graph Theory Appl. 1, No. 1 (2013) 56–76. Cited on pages 58, 63, and 69.
1. C. T. Zamfirescu. Hypohamiltonian graphs and their crossing number, Electron. J. Combin. 19, Iss. 4 (2012) #P12. Cited on pages 1, 2, 5, and 6.


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
      Cited by
3. C. T. Zamfirescu and T. I. Zamfirescu. Every graph occurs as an induced subgraph of some hypohamiltonian graph, J. Graph Theory 88, Iss. 4 (2018) 551–7. Cited on page 551.
3. G. Wiener and C. T. Zamfirescu. Gallai's question and constructions of almost hypotraceable graphs, Discrete Appl. Math. 243 (2018) 270–8. Cited on pages 272, 273, 276, and 277.
3. J. Goedgebeur and C. T. Zamfirescu. Infinitely many planar cubic hypohamiltonian graphs of girth 5, J. Graph Theory 88, Iss. 1 (2018) 40–5. Cited on pages 40 and 44.
3. G. Wiener. New constructions of hypohamiltonian and hypotraceable graphs, J. Graph Theory 87, Iss. 4 (2018) 526–35. Cited on pages 526, 527, and 529.
2. C. T. Zamfirescu. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable, J. Graph Theory 86, Iss. 2 (2017) 223–43. Cited on pages 224, 231, 232, and 239.
2. J. Goedgebeur and C. T. Zamfirescu. Improved bounds for hypohamiltonian graphs, Ars Math. Contemp. 13 (2017) 235–57. Cited on pages 236 and 252.
2. V. Samodivkin. Hypo-efficient domination and hypo-unique domination, Comm. Combin. Optim. 1 (2016) 103–16. Cited on page 104.
1. G. Wiener. On constructions of hypotraceable graphs, Electron. Notes Discrete Math. 54 (2016) 127–32. Cited on pages 128–30.
1. C. T. Zamfirescu. Hypohamiltonian graphs and their crossing number, Electron. J. Combin. 19, Iss. 4 (2012) #P12. Cited on pages 1, 4, and 6.


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
      Cited by
1. A. Shabbir. Fault-tolerant designs in lattice networks on the Klein bottle, Electron. J. Graph Theory Appl. 2, No. 2 (2014) 99–109. Cited on pages 100 and 108.
1. A. Shabbir, C. T. Zamfirescu, and T. Zamfirescu. Intersecting longest paths and longest cycles: A survey, Electron. J. Graph Theory Appl. 1, No. 1 (2013) 56–76. Cited on pages 63 and 64.


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
      Cited by
2. X. Feng, L. Yuan, and T. Zamfirescu. Acute Triangulations of Archimedean Surfaces. The Truncated Tetrahedron, Bull. Math. Soc. Sci. Math. Roumanie 58 (106), No. 3 (2015) 271–82. Cited on page 272.
1. C. T. Zamfirescu. Survey of two-dimensional acute triangulations, Discrete Math. 313, Iss. 1 (2013) 35–49. Cited on page 41.
1. L. Yuan and T. Zamfirescu. Acute triangulations of double planar convex bodies, Publ. Math. Debrecen 81, Iss. 1–2 (2012) 121–6. Cited on page 122.


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
      Cited by
1. X. Feng, L. Yuan, and T. Zamfirescu. Acute Triangulations of Archimedean Surfaces. The Truncated Tetrahedron, Bull. Math. Soc. Sci. Math. Roumanie 58 (106), No. 3 (2015) 271–82. Cited on page 272.
1. C. T. Zamfirescu. Survey of two-dimensional acute triangulations, Discrete Math. 313, Iss. 1 (2013) 35–49. Cited on pages 40, and 42–4.


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
      Cited by
9. G. Golan and S. Shan. Nonempty intersection of longest paths in 2K2-free graphs, Electron. J. Combin. 25, Iss. 2 (2018) #P2.37. Cited on page 2.
8. G. Wiener and C. T. Zamfirescu. Gallai's question and constructions of almost hypotraceable graphs, Discrete Appl. Math. 243 (2018) 270–8. Cited on page 271.
8. J. Gutiérrez. Transversals of Longest Cycles in Chordal and Bounded Tree-Width Graphs, LNCS 10807 (2018) 558–71. Cited on page 570.
7. C. T. Zamfirescu. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable, J. Graph Theory 86, Iss. 2 (2017) 223–43. Cited on page 229.
7. M. Jooyandeh, B. D. McKay, P. R. J. Östergård, V. H. Pettersson, and C. T. Zamfirescu. Planar Hypohamiltonian Graphs on 40 Vertices, J. Graph Theory 84, Iss. 2 (2017) 121–33. Cited on page 132.
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, Discrete Math. 340 (2017) 287–304. Cited on page 288.
6. A. S. Jobson, A. E. Kézdy, J. Lehel, and S. C. White. Detour trees, Discrete Appl. Math. 206 (2016) 73–80. Cited on page 73.
5. Y. Bashir, F. Nadeem, and A. Shabbir. Highly non-concurrent longest paths in lattices, Turk. J. Math. 40 (2016) 21–31. Cited on page 21.
4. F. Joos. A note on longest paths in circular arc graphs, Discuss. Math. Graph Theory 35 (2015) 419–26. Cited on page 419.
3. F. Chen. Nonempty intersection of longest paths in a graph with a small matching number, Czechoslovak Math. J. 65, Iss. 2 (2015) 545–53. Cited on page 546.
1. A. Dino Jumani, C. T. Zamfirescu, and T. I. Zamfirescu. Lattice graphs with non-concurrent longest cycles, Rend. Sem. Mat. Univ. Padova 132 (2014) 75–82. Cited on page 76.
2. A. Shabbir. Fault-tolerant designs in lattice networks on the Klein bottle, Electron. J. Graph Theory Appl. 2, No. 2 (2014) 99–109. Cited on pages 100 and 108.
1. D. Rautenbach and J.-S. Sereni. Transversals of Longest Paths and Cycles, SIAM J. Discrete Math. 28, Iss. 1 (2014) 335–41. Cited on page 335.


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
      Cited by
5. C. Lai. On the size of graphs without repeated cycle lengths, Discrete Appl. Math. 232 (2017) 226–9. Cited on page 227.
4. A. Khodkar, O. Sawin, L. Mueller, and W. H. Choi. (r)-Pancyclic, (r)-Bipancyclic and Oddly (r)-Bipancyclic Graphs, J. Combin. Math. Combin. Comput. 102 (2017) 267–75.
3. S. Liu. Some extremal problems on the cycle length distribution of graphs, J. Combin. Math. Combin. Comput. 100 (2017) 155–71.
2. J. C. George, A. Khodkar, and W. D. Wallis. Pancyclic and Bipancyclic Graphs, SpringerBriefs in Mathematics, 2016, ISBN: 978-3-319-31950-6. Cited on page 38.
1. M. Schaefer. The Graph Crossing Number and its Variants: A Survey, Electron. J. Combin. (2014) #DS21. Cited on pages 27 and 42.


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
      Cited by
10. D. Kröner and M. Rokyta. Error estimates for higher-order finite volume schemes for convection diffusion problems, J. Numer. Math. 26, Iss. 1 (2018) 35–65. Cited on page 38.
09. S. Bau and S. M. Gagola III. Decomposition of closed orientable geometric surfaces into acute geodesic triangles, Arch. Math. 110, Iss. 1 (2018) 81–9. Cited on page 81.
08. A. Joós. Finding equal-diameter tetrahedralizations of polyhedra, Beitr. Algebra Geom. 58 (2017) 679–98. Cited on page 679.
07. C. J. Bishop. Nonobtuse Triangulations of PSLGs, Discrete Comput. Geom. 56 (2016) 43–92. Cited on page 46.
06. L. Yuan. Acute Triangulations of Rectangles, with Angles Bounded Below, in: Convexity and Discrete Geometry Including Graph Theory, Springer Proc. Math. & Stat. 148 (2016), eds.: K. Adiprasito, I. Bárány, and C. Vîlcu, pp. 37–46. Cited on page 37.
05. A. Bezdek and T. Bisztriczky. Finding equal-diameter triangulations in polygons, Beitr. Algebra Geom. 56 (2015) 541–9. Cited on page 542.
04. X. Feng, L. Yuan, and T. Zamfirescu. Acute Triangulations of Archimedean Surfaces. The Truncated Tetrahedron, Bull. Math. Soc. Sci. Math. Roumanie 58 (106), No. 3 (2015) 271–82. Cited on page 272.
03. P. Zanaty and L. T. Dechevsky. On the Numerical Performance of FEM Based on Piecewise Rational Smooth Resolutions of Unity on Triangulations, AIP Conf. Proc. 1570 (2013) 191–203. Cited on page 193.
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, LNCS 8110 (2013) 22–38. Cited on page 34.
01. L. Jia, L. Yuan, C. T. Zamfirescu, and T. I. Zamfirescu. Balanced triangulations, Discrete Math. 313, Iss. 20 (2013) 2178–91. Cited on page 2178.
01. L. Yuan and T. Zamfirescu. Acute triangulations of double planar convex bodies, Publ. Math. Debrecen 81, Iss. 1–2 (2012) 121–6. Cited on page 122.


07. Hypohamiltonian graphs and their crossing number
Electron. J. Combin. 19, Iss. 4 (2012) #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    Journal Link
      Cited by
1. G. Wiener. New constructions of hypohamiltonian and hypotraceable graphs, J. Graph Theory 87, Iss. 4 (2018) 526–35. Cited on pages 526 and 527.
1. C. T. Zamfirescu. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable, J. Graph Theory 86, Iss. 2 (2017) 223–43. Cited on page 224.
1. J. Goedgebeur and C. T. Zamfirescu. Improved bounds for hypohamiltonian graphs, Ars Math. Contemp. 13 (2017) 235–57. Cited on page 253.
1. C. T. Zamfirescu. On hypohamiltonian and almost hypohamiltonian graphs, J. Graph Theory 79, Iss. 1 (2015) 63–81. Cited on page 69.


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
      Cited by
2. A. Shabbir and T. Zamfirescu. Hamiltonicity in k-tree-Halin Graphs, in: Convexity and Discrete Geometry Including Graph Theory, Springer Proc. Math. & Stat. 148 (2016), eds.: K. Adiprasito, I. Bárány, and C. Vîlcu, pp. 59–68. Cited on page 59.
1. B. Schauerte and C. T. Zamfirescu. Small k-pyramids and the complexity of determining k, J. Discrete Alg. 30 (2015) 13–20. Cited on pages 13, 14, 16, and 17.
1. S. Malik, A. M. Qureshi, and T. Zamfirescu. Hamiltonicity of Cubic 3-Connected k-Halin Graphs, Electron. J. Combin. 20, Iss. 1 (2013) #P66. Cited on page 2.


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
      Cited by
1. S. A. van Aardt, A. P. Burger, and M. Frick. An Infinite Family of Planar Hypohamiltonian Oriented Graphs, Graphs Combin. 29, Iss. 4 (2013) 729–33. Cited on page 730.


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
      Cited by
10. C. J. Bishop. Nonobtuse Triangulations of PSLGs, Discrete Comput. Geom. 56 (2016) 43–92. Cited on page 46.
09. L. Yuan. Acute Triangulations of Rectangles, with Angles Bounded Below, in: Convexity and Discrete Geometry Including Graph Theory, Springer Proc. Math. & Stat. 148 (2016), eds.: K. Adiprasito, I. Bárány, and C. Vîlcu, pp. 37–46. Cited on page 37.
08. X. Feng, L. Yuan, and T. Zamfirescu. Acute Triangulations of Archimedean Surfaces. The Truncated Tetrahedron, Bull. Math. Soc. Sci. Math. Roumanie 58 (106), No. 3 (2015) 271–82. Cited on page 272.
07. C. T. Zamfirescu. Improved bounds for acute triangulations of convex polygons, Util. Math. 91 (2013) 71–9. Cited on page 78.
07. C. T. Zamfirescu. Survey of two-dimensional acute triangulations, Discrete Math. 313, Iss. 1 (2013) 35–49. Cited on page 44.
07. L. Yuan and T. Zamfirescu. Acute triangulations of double planar convex bodies, Publ. Math. Debrecen 81, Iss. 1–2 (2012) 121–6. Cited on page 122.
06. X. Feng and L. Yuan. Acute Triangulations of the Cuboctahedral Surface, LNCS 7033 (2011) 73–83. Cited on page 74.
05. L. Yuan. Acute Triangulations of Pentagons, Bull. Math. Soc. Sci. Math. Roumanie 53 (101), Iss. 4 (2010) 393–410. Cited on page 394.
04. L. Yuan. Acute triangulations of trapezoids, Discrete Appl. Math. 158, Iss. 10 (2010) 1121–5. Cited on page 1121.
03. J. Itoh and L. Yuan. Acute triangulations of flat tori, Eur. J. Combin. 30, Iss. 1 (2009) 1–4. Cited on page 2.
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, Discrete Comput. Geom. 37, Iss. 4 (2007) 671–6. Cited on page 672.


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 erroneous: erratum.
      Links
Full text as PDF    Zbl 1120.05054    MR 2336805    DOI: 10.1002/jgt.20241
      Cited by
5. G. Wiener and C. T. Zamfirescu. Gallai's question and constructions of almost hypotraceable graphs, Discrete Appl. Math. 243 (2018) 270–8. Cited on page 271.
5. I. Fabrici, T. Madaras, and M. Timková. Forbidden configurations for hypohamiltonian graphs, Opuscula Math. 38, no. 3 (2018) 357–77. Cited on page 357.
5. C. T. Zamfirescu. On Non-Hamiltonian Graphs for which every Vertex-Deleted Subgraph Is Traceable, J. Graph Theory 86, Iss. 2 (2017) 223–43. Cited on page 224.
4. S. A. van Aardt, A. P. Burger, and M. Frick. The Existence of Planar Hypotraceable Oriented Graphs, Discrete Math. Theor. Comput. Sci. 19, No. 1 (2017) #4. Cited on page 2.
3. J. Goedgebeur and C. T. Zamfirescu. Improved bounds for hypohamiltonian graphs, Ars Math. Contemp. 13 (2017) 235–57. Cited on pages 248 and 249.
3. M. Jooyandeh, B. D. McKay, P. R. J. Östergård, V. H. Pettersson, and C. T. Zamfirescu. Planar Hypohamiltonian Graphs on 40 Vertices, J. Graph Theory 84, Iss. 2 (2017) 121–33. Cited on pages 122 and 126.
3. C. T. Zamfirescu. On hypohamiltonian and almost hypohamiltonian graphs, J. Graph Theory 79, Iss. 1 (2015) 63–81. Cited on pages 64 and 75.
3. F. Nadeem, A. Shabbir, and T. Zamfirescu. Planar Lattice Graphs with Gallai's Property, Graphs Combin. 29, Iss. 5 (2013) 1523–9. Cited on page 1524.
2. A. Shabbir, C. T. Zamfirescu, and T. Zamfirescu. Intersecting longest paths and longest cycles: A survey, Electron. J. Graph Theory Appl. 1, No. 1 (2013) 56–76. Cited on pages 58, 63, 66, and 68.
2. C. T. Zamfirescu. Hypohamiltonian graphs and their crossing number, Electron. J. Combin. 19, Iss. 4 (2012) #P12. Cited on page 1.
2. G. Wiener and M. Araya. On planar hypohamiltonian graphs, J. Graph Theory 67, Iss. 1 (2011) 55–68. Cited on pages 56, 57, 59 and 61.
1. M. Araya and G. Wiener. On cubic planar hypohamiltonian and hypotraceable graphs, Electron. J. Combin. 18, Iss. 1 (2011) #P85. Cited on page 6.
1. B. Schauerte and C. T. Zamfirescu. Regular graphs in which every pair of points is missed by some longest cycle, An. Univ. Craiova, Ser. Mat. Inf. 33 (2006) 154–73. Cited on page 154.


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
      Cited by
1. A. Shabbir, C. T. Zamfirescu, and T. Zamfirescu. Intersecting longest paths and longest cycles: A survey, Electron. J. Graph Theory Appl. 1, No. 1 (2013) 56–76. Cited on page 66.
1. M. Araya and G. Wiener. On cubic planar hypohamiltonian and hypotraceable graphs, Electron. J. Combin. 18, Iss. 1 (2011) #P85. Cited on page 5.
1. C. T. Zamfirescu and T. I. Zamfirescu. A planar hypohamiltonian graph with 48 vertices, J. Graph Theory 55, Iss. 4 (2007) 338–42. Cited on page 341.


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
      Cited by
12. C. J. Bishop. Nonobtuse Triangulations of PSLGs, Discrete Comput. Geom. 56 (2016) 43–92. Cited on page 46.
11. L. Yuan. Acute Triangulations of Rectangles, with Angles Bounded Below, in: Convexity and Discrete Geometry Including Graph Theory, Springer Proc. Math. & Stat. 148 (2016), eds.: K. Adiprasito, I. Bárány, and C. Vîlcu, pp. 37–46. Cited on page 37.
10. X. Feng, L. Yuan, and T. Zamfirescu. Acute Triangulations of Archimedean Surfaces. The Truncated Tetrahedron, Bull. Math. Soc. Sci. Math. Roumanie 58 (106), No. 3 (2015) 271–82. Cited on page 272.
09. C. T. Zamfirescu. Improved bounds for acute triangulations of convex polygons, Util. Math. 91 (2013) 71–9. Cited on page 77.
09. C. T. Zamfirescu. Survey of two-dimensional acute triangulations, Discrete Math. 313, Iss. 1 (2013) 35–49. Cited on page 44.
09. L. Yuan and T. Zamfirescu. Acute triangulations of double planar convex bodies, Publ. Math. Debrecen 81, Iss. 1–2 (2012) 121–6. Cited on page 122.
08. X. Feng and L. Yuan. Acute Triangulations of the Cuboctahedral Surface, LNCS 7033 (2011) 73–83. Cited on page 74.
07. L. Yuan. Acute Triangulations of Pentagons, Bull. Math. Soc. Sci. Math. Roumanie 53 (101), Iss. 4 (2010) 393–410. Cited on page 394.
06. V. Pambuccian. Acute Triangulation of a Triangle in a General Setting, Canad. Math. Bull. 53, Iss. 3 (2010) 534–41. Cited on page 534.
05. L. Yuan. Acute triangulations of trapezoids, Discrete Appl. Math. 158, Iss. 10 (2010) 1121–5. Cited on page 1121.
04. J. Itoh and L. Yuan. Acute triangulations of flat tori, Eur. J. Combin. 30, Iss. 1 (2009) 1–4. Cited on page 2.
03. S. Marcus. Paradigme Universale III. Jocul (Roumanian). Editura Paralela 45, 2007,s ISBN 978-973-47-0196-4. Cited on page 167.
02. L. Yuan and T. Zamfirescu. Acute triangulations of flat Möbius strips, Discrete Comput. Geom. 37, Iss. 4 (2007) 671–6. Cited on page 672.
01. L. Yuan and C. T. Zamfirescu. Acute triangulations of doubly covered convex quadrilaterals, Boll. Unione Mat. Ital., Sez. B, Artic. Ric. Mat. (8) 10, Iss. 3 (2007) 933–8. Cited on page 935.
01. J. Itoh and T. Zamfirescu. Acute triangulations of the regular dodecahedral surface, Eur. J. Combin. 28, Iss. 4 (2007) 1072–86. Cited on page 1073.


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

2018
Spanning subgraphs of planar graphs, 50-minute invited 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, Ghent, 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, Ghent, 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, Ghent, 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, Ghent, 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, Ghent, 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, Ghent, 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).


Miscellanea

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

Conference Organisation
Upcoming and Current
• Since 2017, organiser of the research seminar of our workgroup. If you would like to give a talk, please send me an e-mail at czamfirescu@gmail.com.
Past
• Co-organiser (together with R. Marinescu, C. Vîlcu, and T. Zamfirescu) of the “Bucharest Graph Theory Workshop on How to Span a Graph” held at the University of Bucharest, Roumania, on 15–17 August 2018. For more information, please click here.
• Co-organiser (together with J. Goedgebeur and N. Van Cleemput) of a graph theory workshop on structure and algorithms held at Ghent University, Belgium, on 16–18 August 2017.
For more information, please visit http://www.ggtw.ugent.be/.
• Organiser of a graph theory workshop on longest paths and longest cycles held at Ghent University, Belgium, on 1 and 2 August 2016.
For more information, please visit http://caagt.ugent.be/LPLC/.

Refereed Articles
(2) Ars Combinatoria
(2) Australasian Journal of Combinatorics
(1) Bulletin of the Belgian Mathematical Society - Simon Stevin
(1) Discrete Applied Mathematics
(6) Discrete Mathematics
(1) Discrete Mathematics & Theoretical Computer Science
(1) Electronic Journal of Combinatorics
(7) Graphs and Combinatorics
(1) Journal of Algebra, Combinatorics, Discrete Structures, and Applications
(2) Journal of Graph Theory
(1) Utilitas Mathematica

(13) Summaries for Mathematical Reviews

Teaching   in Dutch
2017/2018 (Spring)   Teaching assistant for the course “Calculus” given by N. Van Cleemput.
2017/2018 (Fall) Lecturer of the course “Wiskunde: algebra”.
2016/2017 (Spring)   Teaching assistant for the course “Calculus” given by N. Van Cleemput.
2016/2017 (Fall) Teaching assistant for the course “Computerproject wiskunde” given by K. Coolsaet.
2015/2016 (Spring) Teaching assistant for the second half of the course “Analyse I” given by N. Van Cleemput.



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