Every 5-connected planar triangulation is 4-ordered Hamiltonian
DOI:
https://doi.org/10.13069/jacodesmath.42463Keywords:
4-ordered, 4-ordered Hamiltonian, Triangulations, Plane graphsAbstract
A graph $G$ is said to be 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 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.
Received: 24 December 2014 | Accepted: 14 March 2015
Downloads
References
D. Archdeacon, N. Hartsfield, and C. H. C. Little, Nonhamiltonian triangulations with large connectivity and representativity, J. Combin. Theory Ser. B 68 (1996) 45-55.
R. J. Faudree, Survey of results on k-ordered graphs, Discrete Math. 229 (2001) 73-87.
W. Goddard, 4-connected maximal planar graphs are 4-ordered, Discrete Math. 257 (2002) 405-410.
J. W. Moon and L. Moser, Simple paths on polyhedra, Pacific J. Math. 13 (1963) 629-631.
R. Mukae and K. Ozeki, 4-connected triangulations and 4-orderedness, Discrete Math. 310(17-18) (2010) 2271-2272.
K. Kawarabayashi and K. Ozeki, 4-connected projective planar graphs are hamiltonian-connected, J. Combin. Theory Ser. B 112 (2015) 124-157.
D. P. Sanders, On paths in planar graphs, J. Graph Theory 24(4) (1997) 341-345.
R. Thomas and X. Yu, 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B 62 (1994) 114-132.
C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983) 169-176.
C. Thomassen, Trees in triangulations, J. Combin. Theory Ser. B 60 (1994) 58-62.
W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956) 99-116.
H. Whitney, A theorem on graphs, Ann. of Math. 32 (1931) 378-390.
X. Yu, Disjoint paths, planarizing cycles, and spanning walks, Trans. Amer. Math. Soc. 349 (1997) 1333-1358.
