BILANGAN RADIO UNTUK GRAF KORONA DARI JALUR DAN SIKEL

MUHAMMAD FAIZ ZULFAN SHOLIHIN, Dr.rer.nat. Yeni Susanti, M.Si. ; Iwan Ernanto, S.Si., M.Sc.

2021 | Skripsi | S1 MATEMATIKA

Pertumbuhan yang sangat cepat dari jaringan nirkabel dan relatif langkanya spektrum radio, mengakibatkan permintaan penempatan frekuensi ke transmiter dengan cara optimal yang kemudian disebut Frequency Assignment Problem (FAP) meningkat dengan sangat signifikan. Salah satu dari FAP yang ada dalam teori graf adalah pewarnaan-k radio-n. Pewarnaan-k radio-n pada sebarang graf G = (V (G); E(G)) adalah suatu fungsi l : V (G) right arrow {0, 1, 2, ... , n} yang memenuhi |l(u)-l(v)| Morethanequal k+1-d(u,v) untuk setiap u, v in V (G) dengan k = diam(G). Sedangkan bilangan radio untuk graf G = (V (G), E(G)) adalah nilai n terkecil sehingga l pada graf G = (V (G), E(G)) memenuhi pewarnaan-k radio-n dan dinotasikan dengan rn(G). Dalam skripsi ini akan dikaji bilangan radio untuk graf Pn odot Cm yang merupakan graf hasil operasi korona dari jalur berorder n dan sikel berorder m. Batas bawah bilangan radio didapat dengan memanfaatkan formula DGNS sedangkan batas atas bilangan radio didapat dengan memanfaatkan formula yang diturunkan dari definisi pewarnaan-k radio-n. Dengan menggunakan batas bawah dan batas atas bilangan radio dapat diperoleh nilai eksak bilangan radio ketika Pn merupakan jalur dengan simpul berjumlah genap dan interval nilai bilangan radio ketika Pn merupakan jalur dengan simpul berjumlah ganjil.

The rapid growth of wireless network, and the lack of radio spectrum, had caused demand of optimal way to assign frequencies to transmiters later on called Frequency Assignment Problem (FAP) significantly rising. One of the FAP existed on graph theory is n-radio k-coloring. An n-radio k-coloring on any graph G = (V (G), E(G)) is a function l : V (G) right arrow {0, 1, 2, ... , n} which satisfies |l(u)-l(v)| lessthanequal k + 1-d(u,v) for each u,v in V (G). While radio number of graph G = (V (G); E(G)) is the smallest possible number of n such that l is a nradio k-coloring on graph G = (V (G), E(G)) for a k = diam(G) and denotated rn(G). In this undergraduate thesis, will be reviewed the radio number of graph Pn odot Cm, which is a corona product of a path of order n and a cycle of order m. The lower bound of radio number is obtained by using formula DGNS while the upper bound is obtained by using formula derived from the definition of n-radio k-coloring itself. Moreover using the lower and upper bound of radio number one obtain the exact value of radio number when Pn is a path of even vertices and the interval value of radio number when Pn is a path of odd vertices.

Kata Kunci : Bilangan Radio, Graf Korona dari Jalur dan Sikel, Formula DGNS