Types of triangle in Hamiltonian triangulations and an application to domination and k-walks

Gunnar Brinkmann, Kenta Ozeki, Nico Van Cleemput


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.


Graph, Hamiltonian cycle, domination, 3-walk

Full Text:


DOI: https://doi.org/10.26493/1855-3974.1733.8c6

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications