Advanced search
1 file | 331.54 KB Add to list

Types of triangle in plane Hamiltonian triangulations and applications to domination and k-walks

Author
Organization
Abstract
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
Graph, Hamiltonian cycle, domination, 3-walk, CYCLES, SETS

Downloads

  • type 0 triangles.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 331.54 KB

Citation

Please use this url to cite or link to this publication:

MLA
Brinkmann, Gunnar, et al. “Types of Triangle in Plane Hamiltonian Triangulations and Applications to Domination and K-Walks.” ARS MATHEMATICA CONTEMPORANEA, vol. 17, no. 1, 2019, pp. 51–66.
APA
Brinkmann, G., Ozeki, K., & Van Cleemput, N. (2019). Types of triangle in plane Hamiltonian triangulations and applications to domination and k-walks. ARS MATHEMATICA CONTEMPORANEA, 17(1), 51–66.
Chicago author-date
Brinkmann, Gunnar, Kenta Ozeki, and Nicolas Van Cleemput. 2019. “Types of Triangle in Plane Hamiltonian Triangulations and Applications to Domination and K-Walks.” ARS MATHEMATICA CONTEMPORANEA 17 (1): 51–66.
Chicago author-date (all authors)
Brinkmann, Gunnar, Kenta Ozeki, and Nicolas Van Cleemput. 2019. “Types of Triangle in Plane Hamiltonian Triangulations and Applications to Domination and K-Walks.” ARS MATHEMATICA CONTEMPORANEA 17 (1): 51–66.
Vancouver
1.
Brinkmann G, Ozeki K, Van Cleemput N. Types of triangle in plane Hamiltonian triangulations and applications to domination and k-walks. ARS MATHEMATICA CONTEMPORANEA. 2019;17(1):51–66.
IEEE
[1]
G. Brinkmann, K. Ozeki, and N. Van Cleemput, “Types of triangle in plane Hamiltonian triangulations and applications to domination and k-walks,” ARS MATHEMATICA CONTEMPORANEA, vol. 17, no. 1, pp. 51–66, 2019.
@article{8641231,
  abstract     = {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.},
  author       = {Brinkmann, Gunnar and Ozeki, Kenta and Van Cleemput, Nicolas},
  issn         = {1855-3966},
  journal      = {ARS MATHEMATICA CONTEMPORANEA},
  keywords     = {Graph,Hamiltonian cycle,domination,3-walk,CYCLES,SETS},
  language     = {eng},
  number       = {1},
  pages        = {51--66},
  title        = {Types of triangle in plane Hamiltonian triangulations and applications to domination and k-walks},
  url          = {http://dx.doi.org/10.26493/1855-3974.1733.8c6},
  volume       = {17},
  year         = {2019},
}

Altmetric
View in Altmetric
Web of Science
Times cited: