Metric Dimension of Graphs Djembe (Dj_n)

Abstract

Let G=(V,E) be a connected graph. For an ordered set A⊆V(G), the representation of a vertex with respect to A is defined by its distance vector to the vertices of A. A set A is called a resolving set if every pair of distinct vertices in G has distinct representations with respect to A. The minimum cardinality of a resolving set is called the metric dimension of G. In this paper, we determine the metric dimension of the Djembe graph D_(j_n ) for n≥3. By constructing appropriate resolving sets and proving their minimality, we obtain an exact formula for the metric dimension. The obtained value depends on the congruence class of n modulo 4, with a special case occurring when n=7. These results provide a new contribution to the study of metric dimensions for cycle-based graph families and extend the existing literature on graph resolvability.

Abstrak
Misalkan G=(V,E) adalah suatu graf terhubung. Untuk suatu himpunan terurut A⊆V(G), representasi sebuah simpul terhadap A didefinisikan sebagai vektor jarak simpul tersebut ke setiap simpul dalam A. Himpunan A disebut himpunan pembeda (resolving set) jika setiap pasangan simpul yang berbeda dalam Gmemiliki representasi yang berbeda terhadap A. Kardinalitas minimum dari himpunan pembeda disebut dimensi metrik (metric dimension) dari graf G. Pada artikel ini ditentukan dimensi metrik dari graf Djembe D_(j_n ) untuk n≥3. Metode yang digunakan adalah konstruksi himpunan pembeda dan pembuktian minimalitasnya untuk memperoleh batas atas dan batas bawah yang berimpit. Hasil penelitian menunjukkan bahwa dimensi metrik graf Djembe dapat dinyatakan secara eksak dalam bentuk formula tertutup yang bergantung pada kelas kongruensi n modulo 4, dengan satu kasus khusus ketika n=7. Hasil ini memberikan kontribusi baru dalam kajian dimensi metrik pada keluarga graf berbasis siklus yang belum pernah diteliti sebelumnya serta memperkaya perkembangan teori resolvabilitas graf.
Kata Kunci: Dimensi metrik, Himpunan pembeda, Representasi simpul, Graf Djembe, Resolvabilitas graf.

2020MSC: 05C12, 05C76.