Jurnal Matematika UNAND (Oct 2024)
KARAKTERISASI POHON DENGAN BILANGAN DOMINASI-LOKASI-METRIK TIGA
Abstract
Misalkan G = (V;E) adalah graf sederhana dan terhubung. Untuk suatu himpunan R = fr1; r2; : : : ; rkg V dan v 2 V , representasi titik v terhadap R adalah vektor r(vjR) = (d(v; r1); d(v; r2); : : : ; d(v; rk)) dimana d(v; r) menyatakan jarak titik v dan titik r. Himpunan R disebut himpunan pembeda dari G jika semua titik di G memiliki representasi unik terhadap R. Himpunan D disebut himpunan dominasi dari G jika setiap titik di G-D bertetangga dengan suatu titik v 2 D. Suatu himpunan dominasi dan juga merupakan himpunan pembeda disebut himpunan dominasi-lokasi-metrik dari G. Kardinalitas dari himpunan dominasi-lokasi-metrik minimum dari G disebut bilangan dominasi-lokasi-metrik dari G. Semua graf orde n dengan bilangan dominasi-lokasi-metrik 1, 2, n-2 dan n-3 telah ditentukan secara lengkap. Dalam tulisan ini, kami mengkarakterisasi semua pohon dengan bilangan-dominasi-lokasi-metrik 3 dan secara khusus membuktikan bahwa tidak ada pohon dengan bilangan-dominasi-lokasi-metrik sama dengan dimensi metriknya.
Keywords