Dimensi k-Metrik pada Graf Double Fan dan Beberapa Graf Terkait

DEDDY RAHMADI, Dr. Yeni Susanti, M.Si

2018 | Tesis | MAGISTER MATEMATIKA

Diberikan graf terhubung dan sederhana G=(V(G), E(G)) dan bilangan bulat positif k. Himpunan S subseteq V(G) disebut sebagai pembangkit k-metrik jika untuk setiap pasang titik berbeda u,v in V(G), terdapat paling sedikit k titik w_1, w_2, ldots, w_k in S sedemikian sehingga d(u,w_{i}) neq d(v,w_{i}) untuk setiap i in {1,2,ldots, k}, dengan d(u,v) adalah panjang path terpendek dari u ke v. Pembangkit k-metrik dengan kardinalitas terkecil disebut basis k-metrik, dan kardinalitas dari basis k-metrik disebut dimensi k-metrik dari graf G yang dinotasikan dim_{k}(G). Pada tesis ini, akan disajikan nilai dari dimensi k-metrik pada graf double fan dan beberapa graf yang terkait dengan double fan, yakni graf double cones, graf double fan snake, graf double fan terpusat, graf parasut diperumum, dan graf parasut diperumum dengan path atas.

Given a connected simple graph G=(V(G),E(G)) and a positive integer k. A set S subseteq V(G) is called a k-metric generator if for any pair of different vertices u,v in V(G), there exist at least k vertices w_, w_, ldots, w_{k} in S such that d(u, w_{i}) neq d(v, w_{i}), for every i in {1,2, ldots, k}, where d(u,v) is the length of a shortest u-v path. A k-metric generator of minimum cardinality is called k-metric basis and its cardinality, the k-metric dimension of G. We define double fan graph as a join graph between null graph of order 2 N_ and path graph of order n P_{n}. In this research we determine the k-metric dimension of double fan graph and some related graph.

Kata Kunci : graf berdimensi k-metrik, basis k-metrik, pembangkit k-metrik, graf double fan