Dimensi Metrik Lokal Dari Graf Circulant

Rimadhany, Ruzika (2017) Dimensi Metrik Lokal Dari Graf Circulant. Masters thesis, Institut Teknologi Sepuluh Nopember.

[img] Text
1214201023-Master_Theses.pdf - Published Version
Restricted to Repository staff only

Download (9MB)

Abstract

Diberikan G adalah graf terhubung dengan dua simpul u dan v. Jarak antara u dan v, dinotasikan d(u,v), didefinisikan sebagai panjang lintasan terpendek dari u ke v pada G. Jika himpunan terurut W={w_1,w_2,w_3,…,w_k} dari simpul-simpul dalam graf terhubung G dan v∈V(G), maka representasi dari v terhadap W adalah r(v│W)=(d(v,w_1 ),d(v,w_2 ),…, d(v,w_k)). Jika r(v|W) untuk setiap v∈V(G) berbeda, maka W dikatakan sebagai himpunan pembeda (resolving set) dari G. Himpunan pembeda dengan banyak anggota minimum disebut dimensi metrik dan dinotasikan dim⁡(G). Apabila r(v|W) untuk setiap dua simpul yang bertetangga di V(G) berbeda dengan v∈V(G), maka W dikatakan sebagai himpunan pembeda lokal (local resolving set) dari G. Himpunan pembeda lokal (local resolving set) dengan banyak anggota minimum disebut dimensi metrik lokal (local metric dimension) dari G yang dinotasikan dengan ldim(G). Pada penelitian ini diperoleh dimensi metrik lokal dari graf circulant circ (n:1) adalah satu untuk n genap dan dua untuk n ganjil. Selanjutnya, dimensi metrik lokal dari graf circulant circ (n:1,2,3,…,⌊(n+1)/2⌋) adalah n-1. Untuk graf circulant circ (n:1,2) dengan n≥4 diperoleh ldim(circ (n:1,2))=2 untuk n ≡2,3 (mod 4), ldim(circ (n:1,2))=3 untuk n ≡0 (mod 4) dan ldim(circ (n:1,2))=4 untuk n ≡1 (mod 4). ===========================================================================================================Let G is a connected graph with two vertices u and v. The distance between u and v, denoted by d(u,v), is defined as length of the shortest path from u to v in G. If an ordered set W={w_1,w_2,w_3,…,w_k} of vertices in a connected graph G and a vertex v of V(G), the representation of v towards W is r(v│W)=(d(v,w_1 ),d(v,w_2 ),…,d(v,w_k)). If r(v|W) for each vertex v∈V(G) is distinct, the set W is a resolving set of G. The resolving set of G with minimum cardinality is a metric dimension and denoted by dim⁡(G). If r(v│W) for every two adjacent vertices of V(G) which v∈V(G) is distinct then the set W is a local resolving set of G. The local resolving set of G with minimum cardinality is a local metric dimension and denoted by ldim(G). The result of research is local metric dimension of circulant graph circ (n:1) is one for n even and two for n odd. Furthermore, local metric dimension of circulant graph circ (n:1,2,3,…,⌊(n+1)/2⌋) is n-1. For circulant graph circ (n:1,2) with n≥4 is ldim(circ (n:1,2))=2 for n ≡2,3 (mod 4), ldim(circ (n:1,2))=3 for n ≡0 (mod 4) and ldim(circ (n:1,2))=4 for n ≡1 (mod 4).

Item Type: Thesis (Masters)
Uncontrolled Keywords: dimensi metrik; dimensi metrik lokal; graf circulant; metric dimension; local metric dimension; circulant graph
Subjects: Q Science > QA Mathematics > QA184 Algebra, Linear
Q Science > QA Mathematics > QA269 Game theory
Divisions: Faculty of Mathematics and Science > Mathematics > (S2) Master Theses
Depositing User: RUZIKA RIMADHANY
Date Deposited: 07 Mar 2017 06:39
Last Modified: 18 Dec 2017 08:03
URI: http://repository.its.ac.id/id/eprint/2791

Actions (login required)

View Item View Item