Research of Carol T. Zamfirescu
Tricube Main Page  --  Last Update: 9th January 2012  --  Contact: czamfirescu@gmail.com

Publications
Citation pages do not include the bibliography.
Erdős number: 3

15. Graphs with single-valued involutive farthest point mapping
In preparation

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

13. On planar hypohamiltonian graphs
Submitted
      Abstract
The smallest known planar hypohamiltonian graph has 42 vertices. We prove that there are further two such graphs of the same order. Then, by showing the existence of planar hypohamiltonian graphs of order 45 and 51, we find a smaller number n0 such that there exist planar hypohamiltonian graphs of all orders n ≥ n0. We decrease n0 from 76 to 48. This, and a theorem on cubic planar hypohamiltonian graphs, improves upon recent results of Araya and Wiener.

12. Small k-pyramids and the complexity of determining k (with B. Schauerte)
Submitted
      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.

11. Lattice graphs with non-concurrent longest cycles (with A. Dino Jumani and T. I. Zamfirescu)
Submitted
      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.

10. Balanced triangulations (with L. Jia, L. Yuan and T. I. Zamfirescu)
Submitted
      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].

9. (2)-pancyclic graphs
Submitted
      Abstract
We introduce the class of (2)-pancyclic graphs, which are simple (i.e., without multiple edges or loops) undirected finite connected graphs of order n having exactly two cycles of length p for all p fulfilling 3 ≤ p ≤ n, analyze their properties, and give several examples of such graphs, among which the smallest.

8. Survey of two-dimensional acute triangulations
Submitted
      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.

7. Improved bounds for acute triangulations of convex polygons
Accepted for publication in Utilitas Mathematica
      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.

6. 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 05956557    DOI: 10.1002/mana.200910058

5. An infinite family of planar non-hamiltonian bihomogeneously traceable oriented graphs
Graphs Combin. 26, No. 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 05815420    DOI: 10.1007/s00373-010-0900-6

4. Acute triangulations of doubly covered convex quadrilaterals (with L. Yuan)
Boll. Unione Mat. Ital., Sez. B, Artic. Ric. Mat. (8) 10, No. 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
      Cited by
6. X. Feng and L. Yuan. Acute Triangulations of the Cuboctahedral Surface, LNCS 7033 (2011) 73-83. Cited on page 74.
5. L. Yuan. Acute Triangulations of Pentagons, Bull. Math. Soc. Sci. Math. Roum. 53 (101), No. 4 (2010) 393-410. Cited on page 394.
4. L. Yuan. Acute triangulations of trapezoids, Discrete Appl. Math. 158, Iss. 10 (2010) 1121-5. Cited on page 1121.
3. J. Itoh and L. Yuan. Acute triangulations of flat tori, Eur. J. Combin. 30, No. 1 (2009) 1-4. Cited on page 2.
2. S. Marcus. Paradigme Universale III. Jocul (Romanian). Editura Paralela 45, 2007, ISBN 978-973-47-0196-4. Cited on page 167.
1. L. Yuan and T. Zamfirescu. Acute triangulations of flat Möbius strips, Discrete Comput. Geom. 37, No. 4 (2007) 671-6. Cited on page 672.
3. A planar hypohamiltonian graph with 48 vertices (with T. I. Zamfirescu)
J. Graph Theory 55, No. 4 (2007) 338-42.      
Remark: Fig. 8 is erroneous; erratum.
      Abstract
We present a planar hypohamiltonian graph on 48 vertices, and derive some consequences.
      Links
Full text as PDF    Zbl 1120.05054    DOI: 10.1002/jgt.20241
      Cited by
2. M. Araya and G. Wiener. On cubic planar hypohamiltonian and hypotraceable graphs, Electron. J. Combin. 18, No. 1 (2011) #P85. Cited on page 6.
1. G. Wiener and M. Araya. On planar hypohamiltonian graphs, J. Graph Theory 67, No. 1 (2011) 55-68. Cited on pages 56, 57, 59 and 61.
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.
2. 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.
      Links
Full text as PDF    Zbl 1174.05419
      Cited by
1. M. Araya and G. Wiener. On cubic planar hypohamiltonian and hypotraceable graphs, Electron. J. Combin. 18, No. 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, No. 4 (2007) 338-42. Cited on page 341.

1. Acute triangulations of the double triangle
Bull. Math. Soc. Sci. Math. Roum. 47 (95), No. 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
      Cited by
8. X. Feng and L. Yuan. Acute Triangulations of the Cuboctahedral Surface, LNCS 7033 (2011) 73-83. Cited on page 74.
7. L. Yuan. Acute Triangulations of Pentagons, Bull. Math. Soc. Sci. Math. Roum. 53 (101), No. 4 (2010) 393-410. Cited on page 394.
6. V. Pambuccian. Acute Triangulation of a Triangle in a General Setting, Canad. Math. Bull. 53, No. 3 (2010) 534-41. Cited on page 534.
5. L. Yuan. Acute triangulations of trapezoids, Discrete Appl. Math. 158, Iss. 10 (2010) 1121-5. Cited on page 1121.
4. J. Itoh and L. Yuan. Acute triangulations of flat tori, Eur. J. Combin. 30, No. 1 (2009) 1-4. Cited on page 2.
3. S. Marcus. Paradigme Universale III. Jocul (Romanian). Editura Paralela 45, 2007, ISBN 978-973-47-0196-4. Cited on page 167.
2. L. Yuan and T. Zamfirescu. Acute triangulations of flat Möbius strips, Discrete Comput. Geom. 37, No. 4 (2007) 671-6. Cited on page 672.
1. L. Yuan and C. T. Zamfirescu. Acute triangulations of doubly covered convex quadrilaterals, Boll. Unione Mat. Ital., Sez. B, Artic. Ric. Mat. (8) 10, No. 3 (2007) 933-8. Cited on page 935.
1. J. Itoh and T. Zamfirescu. Acute triangulations of the regular dodecahedral surface, Eur. J. Combin. 28, No. 4 (2007) 1072-86. Cited on page 1073.
Miscellanea

1. Research Problems from the 18th Workshop '3in1' 2009 (edited by M. Meszka)
Opuscula Math. 30, No. 4 (2010) 527-532.    Full text as PDF

Talks
If you are interested in my slides, please e-mail me.

2011 • Hamiltonian Properties of Generalized Pyramids, held at the 20th Workshop '3in1' 2011 (Hotel "Prezydent", Krynica, Poland) on 24th November.

• Planar hypohamiltonian graphs, held at the International Conference on Research and Education in Mathematics (ICREM) 5 (ITB, Bandung, Indonesia) on 22nd October.

• Planar hypohamiltonian graphs, held at the 20th Workshop on Cycles & Colourings (C&C) (Hotel "Atrium", Nový Smokovec, Slovakia) on 5th September.
• (2)-pancyclic graphs and planar hypohamiltonian graphs, held on 16th August (Hebei Normal University, Shijiazhuang, P.R. China).
• (2)-pancyclic graphs, held at the 4th International Workshop on Optimal Network Topologies (IWONT) (ULB, Brussels, Belgium) on 13th July.
• Planar hypohamiltonian graphs, held in German at the 9th SEG Workshop (CS Dept. TU Chemnitz, Germany) on 28th June.
• Sur les bicyclettes, held in French on 20th May (LMIA, Mulhouse, France).
• (2)-pancyclic graphs, held at the DIMAP Workshop on Combinatorics and Graph Theory (DIMAP, University of Warwick, England) on 10th April.
• Acute Triangulations of Surfaces, held at the 4th International Conference on Combinatorics, Graph Theory, and Applications (Hotel "Am Wald", Elgersburg, Germany) on 25th March.
2010 • Bihomogeneously Traceable Digraphs, held at the International Workshop Combinatorial and Computational Aspects of Optimization, Topology and Algebra (ACCOTA) 2010 (Hotel "Hacienda Real del Caribe", Playa del Carmen, Mexico) on 22nd November.

• Hamiltonian Properties of Generalized Pyramids, held at the 29th Colloquium on Combinatorics (KolKom) (MPII, Saarbrücken, Germany) on 12th November.

• (2)-pancyclic graphs, held at the 19th Workshop on Cycles & Colourings (C&C) (Hotel "Meander", Tatranská Štrba, Slovakia) on 9th September.
• Bihomogeneously Traceable Digraphs, held at the conference Combinatorics 2010 (Hotel "Il Chiostro", Verbania, Italy) on 2nd July.
• Bihomogeneously Traceable Digraphs, held at the Workshop on Hamiltonian Planar Graphs 2010 (ITB, Bandung, Indonesia) on 13th March.
2009 • On Bihomogeneously Traceable Digraphs, held at the 18th Workshop '3in1' 2009 (AGH, Kraków, Poland) on 27th November.
2008 • Hamiltonian Properties of Generalized Pyramids, held on 12th November (LMIA, Mulhouse, France).

Referee Reports

[3] Discrete Math., [1] Electron. J. Combin., [2] Graphs Combin., [1] Util. Math.

Tricube Main Page  --  Contact: czamfirescu@gmail.com