DIMENSI METRIK PADA GRAF SUN, GRAF HELM DANudGRAF DOUBLE CONES

摘要

Bangkit Joko Widodo, 2013. DIMENSI METRIK PADA GRAF SUN,udGRAF HELM DAN GRAF DOUBLE CONES Fakultas Matematika dan IlmuudPengetahuan Alam. Universitas Sebelas Maret.udGraf G terdiri dari himpunan vertex V (G) = {v1; v2; :::; vn} dan himpunanudedge E(G) = {e1; e2; :::; en}. Suatu graf G dikatakan terhubung jika terdapatudlintasan yang menghubungkan setiap vertex pada G. Jarak antara dua vertexudu dan v, dinotasikan d(u; v), adalah panjang lintasan terpendek dari vertex uudke v. Misalkan W = {w1;w2; :::;wn} adalah subhimpunan vertex-vertex dariudgraf terhubung G dan v ∈ V (G), representasi vertex v terhadap W dide�nisikanudsebagai k-pasang terurut r(v|W) = (d(v;w1); d(v;w2); :::; d(v;wk)). HimpunanudW dikatakan sebagai himpunan pembeda dari G jika untuk setiap dua vertexudberbeda x; y ∈ V (G) berlaku r(x|W) ̸= r(y|W). Himpunan pembeda denganudkardinalitas terkecil disebut himpunan pembeda minimum atau basis dari G.udSedangkan banyaknya elemen dari suatu basis di G disebut dimensi metrik dariudG, dinotasikan Dim(G). Dalam penelitian ini diperoleh dimensi metrik pada grafudsun Sn, graf helm Hn dan graf double cones DCn.udKata kunci: dimensi metrik, himpunan pembeda, basis, graf sun, graf helm,udgraf double cones.ududBangkit Joko Widodo, 2013. METRIC DIMENSION OF SUN GRAPH,udHELM GRAPH AND DOUBLE CONES GRAPH. Faculty of Mathematics andudNatural Sciences, Sebelas Maret University.udLet G be a graph with vertex set V (G) = {v1; v2; :::; vn} and edge set E(G) =ud{e1; e2; :::; en}. G is connected if there exists a path connecting every vertex in G.udThe distance between two vertices u and v, denoted by d(u; v), is the length of audshortest path from u to v in G. Let W = {w1;w2; :::;wn} be a subset of verticesudin a connected graph G. For v ∈ V (G), a representation of v with respect toudW is de�ned as the k-tuple r(v|W) = (d(v;w1); d(v;w2); :::; d(v;wk)). The set Wudis called a resolving set of G if every two distinct vertices x; y ∈ V (G) satisfyudr(x|W) ̸= r(y|W). The resolving set of G with minimum cardinality is called audminimum resolving set or basis of G and the cardinality of minimum resolvingudset is called metric dimension, denoted by Dim(G). In this research, we obtainedudthe metric dimensions of a sun graph Sn, a helm graph Hn and a double conesudgraph DCn.udKeywords: metric dimension, resolving set, basis, sun graph, helm graph, doubleudcones graph.