Types of triangle in Hamiltonian triangulations and an application to domination and k-walks - Brinkmann, Gunnar (Ars mathematica contemporanea, 2019)
We investigate the minimum number ?$t_0(G)$? of faces in a Hamiltonian triangulation ?$G$? so that any Hamiltonian cycle ?$C$? of ?$G$? has at least ?$t_0(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.
Keywords: 3-sprehod; 3-walk; dominacija; domination; graf; graph; Hamiltonian cycle; hamiltonski cikel