Cycle Hamilton pada Graf Lengkap, Graf Regular, dan Graf 2-Connected 4-Regular Berorder Kurang dari Sepuluh

Abstract

Suatu graf disebut graf Hamilton apabila graf tersebut memuat cycle Hamilton, yaitu cycle yang melewati setiap vertex tepat satu kali. Menentukan keberadaan cycle Hamilton pada suatu graf dapat menggunakan syarat cukup yang berupa teorema-teorema yang telah diperkenalkan sejak tahun 1950-an. Beberapa syarat cukup yang dibahas dalam karya ilmiah ini adalah syarat cukup yang berhubungan dengan graf lengkap dan graf regular. Suatu graf lengkap berorder 𝑛������ ≥ 3 dan graf r-regular berorder 𝑛������ ≤ 2𝑟������ + 1 merupakan graf Hamilton, Karena kedua graf tersebut memuat cycle Hamilton. Selanjutnya, syarat cukup tersebut digunakan untuk menentukan keberadaan cycle Hamilton pada graf 2-connected 4- regular berorder kurang dari 10.