BibTex RIS Cite

Every 5-connected planar triangulation is 4-ordered Hamiltonian

Year 2015, Volume: 2 Issue: 2, 111 - 116, 30.04.2015

Kenta Ozeki

https://doi.org/10.13069/jacodesmath.42463

Abstract

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.

Keywords

4-ordered 4-ordered Hamiltonian Triangulations Plane graphs

References

  • D. Archdeacon, N. Hartsfield, C. H. C. Little,Nonhamiltonian triangulations with large connectivity and representativity, J. Combin. Theory Ser. B, 68, 45-55, 1996.
  • R. J. Faudree,Survey of results on k-ordered graphs, Discrete Math., 229, 73-87, 2001.
  • W. Goddard, 4-connected maximal planar graphs are 4-ordered, Discrete Math., 257, 405-410, 2002.
  • J. W. Moon and L. Moser,Simple paths on polyhedra, Pacific J. Math., 13, 629-631, 1963.
  • R. Mukae and K. Ozeki, 4-connected triangulations and 4-orderedness, Discrete Math.,310, 2271- 2272, 2010.
  • K. Kawarabayashi and K. Ozeki,4-connected projective planar graphs are hamiltonian-connected, (to appear in) J. Combin. Theory Ser. B.
  • D. P. Sanders,On paths in planar graphs, J. Graph Theory, 24, 341-345, 1997.
  • R. Thomas and X. Yu, 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B, 62, 114-132, 1994.
  • C. Thomassen,A theorem on paths in planar graphs, J. Graph Theory, 7, 169-176, 1983.
  • C. Thomassen,Trees in triangulations, J. Combin. Theory Ser. B, 60, 58-62, 1994.
  • W. T. Tutte,A theorem on planar graphs, Trans. Amer. Math. Soc., 82, 99-116, 1956.
  • H. Whitney,A theorem on graphs, Ann. of Math., 32, 378-390, 1931.
  • X. Yu,Disjoint paths, planarizing cycles, and spanning walks, Trans. Amer. Math. Soc., 349, 1333- 1358, 1997.

Year 2015, Volume: 2 Issue: 2, 111 - 116, 30.04.2015

Kenta Ozeki

https://doi.org/10.13069/jacodesmath.42463

Abstract

References

  • D. Archdeacon, N. Hartsfield, C. H. C. Little,Nonhamiltonian triangulations with large connectivity and representativity, J. Combin. Theory Ser. B, 68, 45-55, 1996.
  • R. J. Faudree,Survey of results on k-ordered graphs, Discrete Math., 229, 73-87, 2001.
  • W. Goddard, 4-connected maximal planar graphs are 4-ordered, Discrete Math., 257, 405-410, 2002.
  • J. W. Moon and L. Moser,Simple paths on polyhedra, Pacific J. Math., 13, 629-631, 1963.
  • R. Mukae and K. Ozeki, 4-connected triangulations and 4-orderedness, Discrete Math.,310, 2271- 2272, 2010.
  • K. Kawarabayashi and K. Ozeki,4-connected projective planar graphs are hamiltonian-connected, (to appear in) J. Combin. Theory Ser. B.
  • D. P. Sanders,On paths in planar graphs, J. Graph Theory, 24, 341-345, 1997.
  • R. Thomas and X. Yu, 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B, 62, 114-132, 1994.
  • C. Thomassen,A theorem on paths in planar graphs, J. Graph Theory, 7, 169-176, 1983.
  • C. Thomassen,Trees in triangulations, J. Combin. Theory Ser. B, 60, 58-62, 1994.
  • W. T. Tutte,A theorem on planar graphs, Trans. Amer. Math. Soc., 82, 99-116, 1956.
  • H. Whitney,A theorem on graphs, Ann. of Math., 32, 378-390, 1931.
  • X. Yu,Disjoint paths, planarizing cycles, and spanning walks, Trans. Amer. Math. Soc., 349, 1333- 1358, 1997.
There are 13 citations in total.

Details

Primary Language English
Journal Section Articles
Authors

Kenta Ozeki This is me

Publication Date April 30, 2015
Published in Issue Year 2015 Volume: 2 Issue: 2

Cite

APA Ozeki, K. (2015). Every 5-connected planar triangulation is 4-ordered Hamiltonian. Journal of Algebra Combinatorics Discrete Structures and Applications, 2(2), 111-116. https://doi.org/10.13069/jacodesmath.42463
AMA Ozeki K. Every 5-connected planar triangulation is 4-ordered Hamiltonian. Journal of Algebra Combinatorics Discrete Structures and Applications. April 2015;2(2):111-116. doi:10.13069/jacodesmath.42463
Chicago Ozeki, Kenta. “Every 5-Connected Planar Triangulation Is 4-Ordered Hamiltonian”. Journal of Algebra Combinatorics Discrete Structures and Applications 2, no. 2 (April 2015): 111-16. https://doi.org/10.13069/jacodesmath.42463.
EndNote Ozeki K (April 1, 2015) Every 5-connected planar triangulation is 4-ordered Hamiltonian. Journal of Algebra Combinatorics Discrete Structures and Applications 2 2 111–116.
IEEE K. Ozeki, “Every 5-connected planar triangulation is 4-ordered Hamiltonian”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 2, no. 2, pp. 111–116, 2015, doi: 10.13069/jacodesmath.42463.
ISNAD Ozeki, Kenta. “Every 5-Connected Planar Triangulation Is 4-Ordered Hamiltonian”. Journal of Algebra Combinatorics Discrete Structures and Applications 2/2 (April 2015), 111-116. https://doi.org/10.13069/jacodesmath.42463.
JAMA Ozeki K. Every 5-connected planar triangulation is 4-ordered Hamiltonian. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2:111–116.
MLA Ozeki, Kenta. “Every 5-Connected Planar Triangulation Is 4-Ordered Hamiltonian”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 2, no. 2, 2015, pp. 111-6, doi:10.13069/jacodesmath.42463.
Vancouver Ozeki K. Every 5-connected planar triangulation is 4-ordered Hamiltonian. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2(2):111-6.