Types of triangle in Hamiltonian triangulations and an application to domination and <i>k</i>-walks

Authors

  • Gunnar Brinkmann
  • Kenta Ozeki
  • Nico Van Cleemput

DOI:

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

Keywords:

Graph, Hamiltonian cycle, domination, 3-walk

Abstract

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.

Published

2019-06-19

Issue

Section

Articles