Indeks Harary Graf Hamilton, Semi-Hamilton dan Hamilton-Kuat

Abstract

Misalkan G sebuah graf terhubung dengan V(G) dan u,v ∈V(G). Jarak titik u dan titik v di G, dilambangkan dengan d(u,v), merupakan suatu lintasan terpendek yang menghubungkan titik u dan titik v di G. Indeks Harary dari graf G, dilambangkan dengan H(G), didefinisikan sebagai berikut: H(G)=∑_(u,v ∈V(G))▒1/(d(u,v)). Pada skripsi ini, indeks Harary suatu graf dijadikan syarat cukup bagi suatu graf agar graf tersebut merupakan graf Hamilton, graf Semi-Hamilton, maupun graf Hamilton-Kuat. Dalam tulisan ini, ditunjukkan bahwa suatu graf merupakan graf Hamilton jika G memenuhi salah satu dari kondisi-kondisi berikut: 1). G graf terhubung dengan n≥3 titik, dan H(G)≥(n^2-2n+2)/2; 2). G graf bipartisi dengan n≥2 titik, dan H(G)≥(〖9n〗^2-3n-4)/6; 3). G graf terhubung-k dengan n titik, dan H(G)≥(2n(n-1)-(k+1)(n-k-1)+1)/4. Ditunjukkan juga bahwa, jika G merupakan graf terhubung dengan n≥4 titik, dan H(G)≥1/2 n^2-3/2 n+5/2, maka G graf semi-Hamilton. Akhirnya, dibuktikan bahwa jika G merupakan sebuah graf terhubung dengan n titik, dan H(G)≥(n^2-2n+3)/2, maka G graf Hamilton-kuat.Kata Kunci: Indeks Harary, Graf Hamilton, Semi-Hamilton, dan Hamilton-Kuat.