Banyaknya Siklus Hamilton pada Graf k-Regular

Abstract

Penelitian ini membahas banyaknya siklus Hamilton pada graf k-regular dengan menitikberatkan pada analisis teoretis melalui konstruksi graf tertentu. Siklus Hamilton merupakan siklus yang melalui setiap simpul dalam graf tepat satu kali dan kembali ke simpul awal, namun keberadaannya tidak selalu dijamin pada graf k-regular. Dengan memanfaatkan teorema-teorema yang memberikan syarat cukup keberadaan siklus Hamilton pada graf k-regular yang 2-terhubung, penelitian ini selanjutnya memfokuskan kajian pada struktur graf yang memungkinkan perhitungan banyaknya siklus Hamilton secara eksplisit. Konstruksi graf G(n,k) yang diperkenalkan oleh Haythorpe digunakan sebagai dasar analisis, di mana graf dibentuk dari gabungan beberapa graf lengkap berorde k+1 dengan pola penghubung tertentu. Melalui analisis struktur dan lintasan Hamilton pada setiap komponen graf, diperoleh rumus eksplisit yang menyatakan banyaknya siklus Hamilton dalam graf G(n,k) sebagai fungsi dari parameter n dan k. Hasil kajian ini menunjukkan bahwa konstruksi graf memainkan peran penting dalam menentukan banyaknya siklus Hamilton pada graf k-regular.

This study investigates the number of Hamiltonian cycles in k-regular graphs, with an emphasis on theoretical analysis through specific graph constructions. A Hamiltonian cycle is a cycle that visits each vertex of a graph exactly once and returns to the starting vertex; however, its existence is not guaranteed in all k-regular graphs. By employing sufficient conditions that ensure the existence of Hamiltonian cycles in 2-connected k-regular graphs, this study focuses on graph structures that allow the explicit counting of Hamiltonian cycles. In particular, the construction of the graph G(n,k), introduced by Haythorpe, is used as the main analytical framework, where the graph is formed by combining several complete graphs of order k+1 with a specific pattern of connecting edges. Through an analysis of the graph structure and the corresponding Hamiltonian traversals within each component, an explicit formula for the number of Hamiltonian cycles in G(n,k) is obtained as a function of n and k. The results demonstrate that graph construction plays a crucial role in determining the number of Hamiltonian cycles in k-regular graphs.