FUNGSI DOMINASI ROMAWI PADA LINE GRAPH

Abstract

Himpunan D disebut himpunan dominasi pada graf G=(V,E) jika setiap simpul dari himpunan V-D berikatan dengan paling sedikit satu simpul pada D. Pada penelitian ini dibahas mengenai fungsi dominasi Romawi dari suatu line graph. Line graph L(G) dari suatu graf G adalah graf yang merepresentasikan himpunan sisi dari G dan hubungan antara sisi-sisi pada G. Simpul-simpul pada L(G) dibentuk dari himpunan sisi G. Fungsi f disebut fungsi dominasi Romawi pada L(G) jika dan hanya jika untuk setiap simpul v'∈’V', f :V'→{0,1,2} dan untuk setiap simpul v'i dengan f(v'i)=0 berikatan dengan paling sedikit satu simpul v'j dengan f(v'j)=2. Himpunan V'0, V'1 dan V'2 merupakan subhimpunan dari V' yang dipengaruhi oleh fungsi f dengan V'i={v'∈V'│f(v')=i} untuk i=0,1,2. Himpunan D' disebut himpunan dominasi Romawi pada L(G) jika D'= V'1∪’V'2 dan f(V')=|V'1|+2|V'2| merupakan bobot fungsi dominasi Romawi. Bilangan dominasi Romawi pada L(G) dinotasikan dengan γr(L(G)) yang merupakan nilai minimum dari f(V').

Kata Kunci: Himpunan Dominasi, Bilangan Dominasi Romawi, Graf Terhubung