DIMENSI METRIK KUAT PADA GRAF

Abstract

Diberikan graf sederhana terhubung 𝐺 dan non-trivial dengan himpunan vertex 𝑉(𝐺) dan himpunan edge 𝐸(𝐺). Interval antara 𝑢 dan𝑣 atau 𝐼[𝑢,𝑣] di 𝐺 merupakan kumpulan vertex yang terdapat pada path terpendek 𝑢 − 𝑣. Misal 𝑆 = {𝑠 ,𝑠2,…,𝑠𝑘} adalah subhimpunan dari 𝑉(𝐺), 𝑆 dikatakan sebagai himpunan pembeda kuat dari 𝐺 jika untuk setiap dua vertex 𝑢 dan 𝑣 dari V(G) dibedakan kuat oleh suatu vertex di 𝑆. Suatu vertex 𝑠 ∈ 𝑉(𝐺) disebut pembeda kuat untuk dua vertex 𝑢,𝑣 ∈ 𝑉(𝐺) jika 𝑣 ∈ 𝐼[𝑢,𝑠] atau 𝑢 ∈ 𝐼[𝑣,𝑠]. Kardinalitas minimum dari himpunan pembeda kuat disebut basis metrik kuat. Banyaknya elemen basis metrik kuat disebut juga dimensi metrik kuat. Dimensi metrik kuat dari suatu graf 𝐺 dinotasikan dengan 𝑠𝑑𝑖𝑚(𝐺). Pada penelitian ini diperoleh dimensi metrik kuat pada graf, khususnya dimensi metrik kuat pada graf dipyramidal korona graf null 𝐷𝑃 ⊙ 𝑁  dengan 𝑛 ≥ 3,𝑚 ≥ 1 dan graf wheel korona graf path 𝑊 ⊙ 𝑃 dengan 𝑛 ≥ 4,𝑚 ≥ 2. Metode yang digunakan adalah kajian pustaka. Didapat dimensi metrik kuat pada graf dipyramidal korona graf null yaitu 𝑠𝑑𝑖𝑚(𝐷𝑃 ⊙ 𝑁 ) = (𝑛 + 2)𝑚 − 1 dan graf wheel korona graf path yaitu 𝑠𝑑𝑖𝑚(𝑊 ⊙ 𝑃) = 𝑚𝑛 − 1 untuk 𝑛 ≥ 4,𝑚 = 2 dan 𝑚𝑛 − 2 untuk 𝑛 ≥ 4, 𝑚 ≥ 3.