1. bookVolume 30 (2022): Issue 1 (February 2022)
Journal Details
License
Format
Journal
eISSN
1844-0835
First Published
17 May 2013
Publication timeframe
1 time per year
Languages
English
access type Open Access

Generating punctured surface triangulations with degree at least 4

Published Online: 12 Mar 2022
Volume & Issue: Volume 30 (2022) - Issue 1 (February 2022)
Page range: 129 - 151
Received: 22 Apr 2021
Accepted: 25 Jul 2021
Journal Details
License
Format
Journal
eISSN
1844-0835
First Published
17 May 2013
Publication timeframe
1 time per year
Languages
English
Abstract

As a sequel of a previous paper by the authors, we present here a generating theorem for the family of triangulations of an arbitrary punctured surface with vertex degree ≥ 4. The method is based on a series of reversible operations termed reductions which lead to a minimal set of triangulations in such a way that all intermediate triangulations throughout the reduction process remain within the family. Besides contractible edges and octahedra, the reduction operations act on two new configurations near the surface boundary named quasi-octahedra and N-components. It is also observed that another configuration called M-component remains unaltered under any sequence of reduction operations. We show that one gets rid of M-components by flipping appropriate edges.

Keywords

MSC 2010

[1] D.W. Barnette, A. L. Edelson, All 2−manifolds have finitely many minimal triangulations, Israel J. Math. 67 (1989), 123-128.10.1007/BF02764905 Search in Google Scholar

[2] G. Brinkmann, B. D McKay Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58(2) (2007), 323-357. Search in Google Scholar

[3] A. Boulch, É. Colin de Verdière, A. Nakamoto, Irreducible triangulations of surfaces with boundary, Graphs Comb., 29 No. 6 (2013), 1675–1688. Search in Google Scholar

[4] M.J. Chávez, S. Lawrencenko, A. Quintero, M. T. Villar, Irreducible triangulations of the Möbius band, Bul. Acad. Sţiinţe Repub. Mold. Mat., No. 2(75) (2014), 44–50. Search in Google Scholar

[5] M.J. Chávez, S. Negami, A. Quintero, M. T. Villar, Generating families of surface triangulations. The case of punctured surfaces with inner degree at least 4. arXiv e-print service, Cornell University Library, http://arxiv.org/abs/1507.03975v2, (2015). Search in Google Scholar

[6] M.J. Chávez, S. Negami, A. Quintero, M. T. Villar, A generating theorem of punctured surface triangulations with inner degree at least 4. Math. Slovaca 69, No. 5 (2019), 969–978. Search in Google Scholar

[7] D. Fernández-Ternero, E. Macías-Virgós, N. A. Scoville, J. A. Vilches Strong Discrete Morse Theory and Simplicial L-S Category: A Discrete Version of the Lusternik-Schnirelmann Theorem, Discret. Comput. Geom. 63 (2020), 607-623.10.1007/s00454-019-00116-8 Search in Google Scholar

[8] J. Fujisawa, A. Nakamoto, K. Ozeki, Hamiltonian cycles in bipartite toroidal graphs with a partite set of degree four vertices, J. Combin. Theory, Ser. B 103 (2013), 46-60. Search in Google Scholar

[9] B. Grunbaum, Polytopes, graphs, and complexes, Bull. Amer. Math. Soc. 76 (1970), 1131-1201.10.1090/S0002-9904-1970-12601-5 Search in Google Scholar

[10] K. Kawarabayashi, K. Ozeki, 4-connected projective-planar graphs are Hamiltonian-connected, J. Combin. Theory Ser. B 112 (2015), 36-69.10.1016/j.jctb.2014.11.006 Search in Google Scholar

[11] H. Komuro, A. Nakamoto, S. Negami, Diagonal flips in triangulations on closed surfaces whith minimum degree at least 4, J. Combin. Theory Ser. B 76 (1999), 68-92.10.1006/jctb.1998.1889 Search in Google Scholar

[12] B. Krüger, K. Mecke, Genus dependence of the number of (non-) orientable surface triangulations, Phys. Rev. D 93 (2016), 085018 (6 pp).10.1103/PhysRevD.93.085018 Search in Google Scholar

[13] S. Lawrencenko, T. Sulanke, M. T. Villar, L. V. Zgonnik, M. J. Chávez, J. R. Portillo. Irreducible triangulations of the once-punctured torus, Sibirskie Elektronnye Matematicheskie Izvestiya. Vol. 15 (2018), 277-304. Search in Google Scholar

[14] A. Malnič, R. Nedela, K-Minimal triangulations of surfaces, Acta Math. Univ. Comenianae 64, 1 (1995), 57-76. Search in Google Scholar

[15] N. Matsumoto, A. Nakamoto, Generating 4-connected even triangulations on the sphere, Discrete Math. 338 (2015), 64-70.10.1016/j.disc.2014.08.017 Search in Google Scholar

[16] N. Matsumoto, A. Nakamoto, T. Yamaguchi, Generating even triangulations on the torus, Discrete Mathematics 341 (2018), 2035-2048.10.1016/j.disc.2018.04.002 Search in Google Scholar

[17] A. Nakamoto, H. Motoaki, Generating 4-connected triangulations on closed surfaces, Mem. Osaka Kyoiku Univ. Ser. III Nat. Sci. Appl. Sci. 50, no. 2 (2002), 145-153. Search in Google Scholar

[18] A. Nakamoto, S. Negami, Generating triangulations on closed surfaces with minimum degree at least 4, Discrete Math. 244 (2002), 345-349.10.1016/S0012-365X(01)00093-0 Search in Google Scholar

[19] S. Negami, Triangulations, Handbook of Graph Theory, Second Edition. J. L. Gross, J. Yellen and P. Zhang (Ed.) Chapman and Hall/CRC Press, 876-901, 2014.10.1201/b16132-52 Search in Google Scholar

[20] M. Nishina, Y. Suzuki, A generating theorem of simple even triangulations with a finitizable set of reductions, Discrete Math., 340 (2017), 2604-2613.10.1016/j.disc.2017.06.018 Search in Google Scholar

[21] T. Sulanke, Generating irreducible triangulations of surfaces, arXiv:math/0606687v1 [math.CO], (2006). Search in Google Scholar

[22] T. Sulanke, F. H. Lutz, Isomorphism-free lexicographic enumeration of triangulated surfaces and 3-manifolds, Eur. J. Comb. 30 (2009), 1965-1979.10.1016/j.ejc.2008.12.016 Search in Google Scholar

[23] R. Thomas, X. Yu, 4-connected projective planar graphs are Hamiltonian, J. Combin. Theory Ser. B 62 (1994), 114-132.10.1006/jctb.1994.1058 Search in Google Scholar

[24] H. Whitney, A theorem on graphs, Ann. Math. 32 (1931), 378-390.10.2307/1968197 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo