Artikel ini membahas tentang pelabelan Fibonacci prima ke-k pada sebuah graf sederhana G dengan himpunan simpul V(G) dan himpunan sisi E(G). Suatu graf G adalah graf Fibonacci prima ke-k jika terdapat pemetaan injektif f:V(G)→{F_k,F_(k+1),…,F_(k+n-1)} yang memetakan himpunan simpul V(G) ke himpunan bagian bilangan Fibonacci {F_k,F_(k+1),…,F_(k+n-1)}. F_k merupakan bilangan Fibonacci yang berada pada urutan ke-k dimana k≤n dan k,n∈N. Untuk setiap sisi uv∈E(G) dengan u,v∈V(G) berlaku f^* (uv)=gcd(f(u),f(v))=1 dengan f^*:E(G)→N. Graf yang digunakan dalam penelitian ini adalah graf H dengan orde lebih besar atau sama dengan tiga dan graf ulat H_n dengan orde lebih besar atau sama dengan dua. Penelitian ini bertujuan untuk mengkontruksi pelabelan Fibonacci prima ke-k pada graf H dan graf ulat H_n serta membuktikan bahwa graf tersebut adalah graf Fibonacci prima ke-k.