Every 5-connected planar triangulation is 4-ordered Hamiltonian
Author(s) -
Kenta Ozeki
Publication year - 2015
Publication title -
journal of algebra combinatorics discrete structures and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.137
H-Index - 1
ISSN - 2148-838X
DOI - 10.13069/jacodesmath.42463
Subject(s) - planar , triangulation , hamiltonian (control theory) , computer science , combinatorics , mathematics , geometry , computer graphics (images) , mathematical optimization
A graph $G$ is said to be \textit{$4$-ordered} if for any ordered set of four distinct vertices of $G$, there exists a cycle in $G$ that contains all of the four vertices in the designated order. Furthermore, if we can find such a cycle as a Hamiltonian cycle, $G$ is said to be \textit{$4$-ordered Hamiltonian}. It was shown that every $4$-connected planar triangulation is (i) Hamiltonian (by Whitney) and (ii) $4$-ordered (by Goddard). Therefore, it is natural to ask whether every $4$-connected planar triangulation is $4$-ordered Hamiltonian. In this paper, we give a partial solution to the problem, by showing that every $5$-connected planar triangulation is $4$-ordered Hamiltonian.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom