• Putti Naura Adwita Department of Mathematics, University of Riau, Indonesia
  • Sri Gemawati Department of Mathematics, University of Riau, Indonesia




Petersen graph, generalized Petersen graph, Hamiltonian, Hypohamiltonian


This article discusses the Hamiltonian and Hypohamiltonian properties of Generalized Petersen Graphs GPn,6. A Hamiltonian graph is a graph that has a Hamiltonian cycle. So, a graph is called to be Hamiltonian and has a cycle that passes through each vertex exactly once. A Hypohamiltonian graph is if it is not a Hamiltonian graph, but if one vertex is removed it will be Hamiltonian. The Petersen graph is a cubic graph with ten vertices and fifteen edges and each vertex is of degree three. The generalized Petersen graph is denoted GPn,k, for positive numbers n and k with 2 ≤ 2k < ????. The Petersen graph is not a Hamiltonian graph, but is Hypohamiltonian. In the Generalized Petersen graph for GPn,6  for n ≡ 1(mod 13), n ≡ 3(mod 13), n ≡ 7(mod 13), n ≡ 9(mod 13) is a Hamiltonian, for n ≡ 0(mod 13) is a hypohamiltonian, and for n ≡ 2(mod 13), n ≡ 4(mod 13), n ≡ 5(mod 13), n ≡ 6(mod 13), n ≡ 8(mod 13) neither.


Chen, F., and Fan, G., Fulkerson-Covers of Hypohamiltonian Graphs, 2015, Discrete Applied Mathematics, Volume:186 pp 66-73.

Chia, G., L., Ong, S., H., and Arumugam, S., Hamilton Cycles in Cubic Graphs, 2007, International Journal of Graphs and Combinatorics, Volume:3 pp 251-259.

Deo, N., 1989., Graph Theory with Applications to Engineering and Computer Science, Dover Publication, inc, New York.

Frick, M., and Singleton, J., Cubic Maximal Nontraceable Graphs, 2007, Discrete Mathematics, Volume: 307 pp 885-891.

Ginting, J., and Banjarnahor, H., Petersen Graphs with Some Related Properties in Graph Theory, 2016, Karismatika, Volume:2.

Kusmira, M., and Taufiqurrochman, Utilization of Graph Applications in Making the 05 Tasikmalaya Public Transportation Route, 2017.

Makalew, R., A., M., Montolalu, C., E., J., C., and Mananoas, M., L., Hamiltonian Path in 4-Connected Graphs, 2020, Journal of Mathematics and Applications, Volume:9 pp 181-188.

Munir, R., 2010., Discrete Mathematics 4th Edition, Informatika, Bandung.

Potanka, K., S.,1998., Groups, Graphs, and Symmetry-Breaking, M.Sc Thesis, Faculty of the

Virginia Polytechnic Institute and State University.

Ryjacek, Z., Vrana, P., and Xiong, L., Hamiltonian Properties of 3-Connected Caw, Hourglass-Free Graphs, 2018, Discrete Mathematics, Volume: 341 pp1806-1815.

Slamin, 2023., Graph Theory and Its Applications Second Edition, R12 Group, Surabaya.

Wallis, W., D., 2007., A Beginner’s Guide to Graph Theory Second Edition, Bikhauser, Boston.

West, D., B., 2001., Introduction to Graph Theory Second Edition, Universitas Illinois, Urban.

Imam, D., 2012., Sifat Hamiltonian dan Hipohamiltonian pada Graf Petersen Diperumum (GPn,1 & GPn,2), Skripsi, Universitas Islam Maulana Malik Ibrahim.