Types of triangle in Hamiltonian triangulations and an application to domination and k-walks
Gunnar Brinkmann, Kenta Ozeki, Nico Van Cleemput · Ars Mathematica Contemporanea · 2019
We investigate the minimum number t0(G) of faces in a Hamiltonian triangulation G so that any Hamiltonian cycle C of G has at least t0(G) faces that do not contain an edge of C. We prove upper and lower bounds on the maximum of these numbers for all triangulations with a fixed number of facial triangles. Such triangles play an important role when Hamiltonian cycles in triangulations with 3-cuts are constructed from smaller Hamiltonian cycles of 4-connected subgraphs. We also present results linking the number of these triangles to the length of 3-walks in a class of triangulation and to the domination number.