1. bookVolumen 30 (2022): Edición 1 (February 2022)
Detalles de la revista
License
Formato
Revista
eISSN
1844-0835
Primera edición
17 May 2013
Calendario de la edición
1 tiempo por año
Idiomas
Inglés
access type Acceso abierto

Generating punctured surface triangulations with degree at least 4

Publicado en línea: 12 Mar 2022
Volumen & Edición: Volumen 30 (2022) - Edición 1 (February 2022)
Páginas: 129 - 151
Recibido: 22 Apr 2021
Aceptado: 25 Jul 2021
Detalles de la revista
License
Formato
Revista
eISSN
1844-0835
Primera edición
17 May 2013
Calendario de la edición
1 tiempo por año
Idiomas
Inglés
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

Artículos recomendados de Trend MD

Planifique su conferencia remota con Sciendo