Pelabelan Prima pada Graf Franklin

Miftah Alfiqiyatul Luthfi, Uha Isnaini, S.Si., M.Sc., Ph.D.

2025 | Skripsi | MATEMATIKA

Diberikan graf sederhana dan tak berarah G = (V (G),E(G)) dengan pelabelan prima sebagai fungsi bijektif dari himpunan titik V (G) ke himpunan bilangan bulat positif {1, 2, . . . , |V (G)|}, sedemikian sehingga setiap pasangan titik yang bertetangga memiliki label yang relatif prima. Graf G yang memenuhi sifat ini disebut graf prima. Dalam skripsi ini dibahas pelabelan prima pada Graf Franklin serta sifat keprimaannya terhadap beberapa operasi graf, yaitu duplikasi titik, pertukaran titik, dan gabungan lintasan yang diperluas. Selanjutnya, ditelaah hubungan isomorfisme antar berbagai bentuk Graf Franklin serta pelabelan prima pada masing-masing bentuk tersebut.

Given a simple undirected graph G = (V (G),E(G)) with a prime labeling defined as a bijective function from the vertex set V (G) to the set of positive integers {1, 2, . . . , |V (G)|}, such that every pair of adjacent vertices has relatively prime labels. A graph G that satisfies this condition is called a prime graph. This undergraduate thesis discusses the prime labeling of the Franklin Graph and its primality properties under several graph operations, namely vertex duplication, vertex switching, and extended path union. Next, the isomorphism relationships among various forms of the Franklin graph and the prime labeling on each of these forms are examined.

Kata Kunci : Graf prima, Pelabelan prima, Graf Franklin, Operasi graf, Isomorfisme graf