Generating punctured surface triangulations with degree at least 4

Chávez, María-José; Negami, Seiya; Quintero, Antonio; Villar-Liñán, María Trinidad

doi:10.2478/auom-2022-0008

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.

References

[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 Back to article
[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 Back to article
[3] A. Boulch, É. Colin de Verdière, A. Nakamoto, Irreducible triangulations of surfaces with boundary, Graphs Comb., 29 No. 6 (2013), 1675–1688.10.1007/s00373-012-1244-1
Search in Google Scholar Back to article
[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 Back to article
[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 Back to article
[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.10.1515/ms-2017-0281
Search in Google Scholar Back to article
[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 Back to article
[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.10.1016/j.jctb.2012.08.004
Search in Google Scholar Back to article
[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 Back to article
[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 Back to article
[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 Back to article
[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 Back to article
[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 Back to article
[14] A. Malnič, R. Nedela, K-Minimal triangulations of surfaces, Acta Math. Univ. Comenianae 64, 1 (1995), 57-76.
Search in Google Scholar Back to article
[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 Back to article
[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 Back to article
[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 Back to article
[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 Back to article
[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 Back to article
[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 Back to article
[21] T. Sulanke, Generating irreducible triangulations of surfaces, arXiv:math/0606687v1 [math.CO], (2006).
Search in Google Scholar Back to article
[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 Back to article
[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 Back to article
[24] H. Whitney, A theorem on graphs, Ann. Math. 32 (1931), 378-390.10.2307/1968197
Search in Google Scholar Back to article

Generating punctured surface triangulations with degree at least 4

Abstract

Paradigm

My account