PELABELAN k-PRIMA PADA BEBERAPA KELAS GRAF GABUNGAN LINTASAN

FIRDHA NURHIDAYAH, Dr.rer.nat. Yeni Susanti, S.SI., M.SI.

2021 | Tesis | MAGISTER MATEMATIKA

Abstrak. Diberikan graf sederhana, terhubung, dan tidak berarah G=(V(G),E(G)) dengan V(G) himpunan simpul tak kosong dan E(G) himpunan sisi. Diberikan fungsi injektif f:V(G) dipetakan ke {k,k+1,k+2,...,k +|V(G)|-1} untuk suatu bilangan bulat k dan fungsi f berpangkat +:E(G)dipetakan ke N dengan f berpangkat+ (uv)=gcd(f(u),f(v)), untuk semua uv di E(G). Fungsi f disebut pelabelan k-prima jika f berpangkat + (uv)=1, untuk semua uv di E(G) . Graf G disebut graf k- prima jika graf tersebut dapat dilabeli dengan pelabelan k-prima. Selanjutnya, pada tulisan ini akan dibahas mengenai pelabelan k-prima pada beberapa graf seperti graf siklus C_2n, untuk n lebih besar atau sama dengan 2, graf siklus C_3, C_5, C_9, graf tadpole Tn,m untuk n lebih besar atau sama dengan 3 dan m lebih besar atau sama dengan 1, graf subdivisi barycentric C_n(C_n) untuk n lebih besar atau sama dengan 3, graf Y-pohon P_n berpangkat 3 untuk n lebih besar atau sama dengan 1, graf X-pohon P_n berpangkat 4 untuk n lebih besar atau sama dengan 1 , graf gabungan lintasan pada satu titik P_n berpangkat t untuk n lebih besar atau sama dengan 1 dan t lebih besar atau sama dengan 5, graf P_n,Cm dot mK_1,r untuk n lebih besar atau sama dengan 3, m=3,4,5, dan r lebih besar atau sama dengan 2, serta graf P_n(P_q, K_1) untuk n lebih besar atau sama dengan 2 dan q genap.

Let G=(V(G),E(G)) be a simple graph, connected, and undirected graph with non empty vertex set V(G) and edge set E(G). Let f:V(G) maps to {k,k+1,k+2,...,k+|V(G)|-1} be an injective function and let a function f power +:E(G) maps to N with f power + (uv)=gcd(f(u),f(v)), for all uv in E(G). f is called k-prime labeling if f power + (uv)=1, for all uv in E(G). A graph G is called a k-prime graph if a graph G can be labeled k-prime labeling . In this paper, it will be discussed about k-prime labeling of some graphs such as cycle graph C_2n for n greater than or equal to 2, cycle graph C_3, C_5, C_9, tadpole graph Tn,m for n greater than or equal to 3 and m greater than or equal to 1, subdivisi barycentric graph C_n(C_n) for n greater than or equal to 3, Y-tree graph P_n power 3 for n greater than or equal to 1, X-tree graph P_n power 4 for n greater than or equal to 1, one point union of path graphs P_n power t for n greater than or equal to 1 and t greater than or equal to 5, P_n,Cm circled dot operator mK_1,r for n greater than or equal to 3, m=3,4,5, and r greater than or equal to 2, and also P_n(P_q, K_1) for n greater than or equal to 2 and q even.

Kata Kunci : pelabelan prima, pelabelan k-prima, graf gabungan lintasan pada satu titik, graf P_n,Cm dot mK_1,r, graf P_n (P_q,K_1)