Dimensi Metrik Periferal Dan Dimensi Metrik Monofonik Periferal Pada Graf

Tarisma, Tantri (2025) Dimensi Metrik Periferal Dan Dimensi Metrik Monofonik Periferal Pada Graf. Masters thesis, Institut Teknologi Sepuluh Nopember.

Text 6002231002_Master_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (2MB) | Request a copy

Abstract

Diberikan G adalah graf terhubung dengan himpunan simpul V(G) = {v_1, v_2, ..., v_k} dan himpunan sisi E(G) = {e_1, e_2, ..., e_k}. Himpunan terurut W = {w_1, w_2, ..., w_k} merupakan himpunan bagian dari V(G). Jarak d(u,v) adalah panjang lintasan terpendek antara simpul u dan v, sedangkan jarak monofonik d_m(u,v) adalah panjang lintasan terpanjang antara simpul u dan v yang tidak memuat tali busur. Representasi r(v | W) dari simpul v terhadap himpunan terurut W dinyatakan sebagai k-tuple (d(v, w_1), d(v, w_2), ..., d(v, w_k)), di mana W disebut himpunan pembeda periferal dari G jika untuk setiap pasangan simpul berbeda u, v ∈ V(G), berlaku r(u | W) ≠ r(v | W). Himpunan terurut W dengan kardinalitas minimal disebut basis untuk G dan kardinalitas |W| disebut dimensi metrik periferal dari G, dituliskan dim(G). Representasi monofonik r_m(v | W_m) dari simpul v terhadap himpunan terurut W_m didefinisikan sebagai k-tuple (d_m(v, w_1), d_m(v, w_2), ..., d_m(v, w_k)), di mana W_m disebut himpunan pembeda monofonik periferal dari G jika untuk setiap pasangan simpul berbeda u, v ∈ V(G), berlaku r_m(u | W_m) ≠ r_m(v | W_m). Himpunan terurut W_m dengan jumlah elemen minimal disebut basis monofonik untuk G dan kardinalitas |W_m| disebut dimensi metrik monofonik periferal dari G, dituliskan mdim(G). Penelitian ini menentukan nilai dim(G) dan mdim(G) untuk graf-graf dasar G yaitu P_n, C_n, K_n, S_n, graf abjad, serta graf hasil operasi korona lingkungan tertutup antara graf G dan K_1. Analisis menunjukkan bahwa untuk setiap graf terhubung G berlaku d(v,u) ≤ d_m(v,u) dan dim(G) ≤ mdim(G), serta jika G merupakan graf pohon, maka d(v,u) = d_m(v,u) untuk setiap pasangan simpul v,u ∈ V(G), sehingga diperoleh dim(G) = mdim(G).
======================================================================================================================================
Given a connected graph G with vertex set V(G) = {v_1, v_2, ..., v_k} and edge set E(G) = {e_1, e_2, ..., e_k}, let W = {w_1, w_2, ..., w_k} be an ordered subset of V(G). The distance d(u,v) is defined as the length of the shortest path between vertices u and v, while the monophonic distance d_m(u,v) is the length of the longest path between u and v that does not contain any chord. The representation r(v | W) of a vertex v with respect to W is expressed as the k-tuple (d(v, w_1), d(v, w_2), ..., d(v, w_k)), where W is called a \textit{peripheral resolving set} of G if, for every pair of distinct vertices u, v ∈ V(G), r(u | W) ≠ r(v | W). An ordered set W with minimal cardinality is called a \textit{basis} for G, and its cardinality |W| is the \textit{peripheral metric dimension} of G, denoted dim(G). Similarly, the monophonic representation r_m(v | W_m) with respect to an ordered set W_m is given by the k-tuple (d_m(v, w_1), d_m(v, w_2), ..., d_m(v, w_k)), where W_m is a \textit{monophonic peripheral resolving set} of G if r_m(u | W_m) ≠ r_m(v | W_m) for all distinct u, v ∈ V(G). An ordered set W_m with minimal cardinality is referred to as a \textit{monophonic basis} for G, and its cardinality |W_m| is the \textit{monophonic peripheral metric dimension}, mdim(G). This study determines the values of dim(G) and mdim(G) for basic graphs where G is P_n, C_n, K_n, S_n, alphabet graphs, and graphs obtained from the closed neighborhood corona operation between G and K_1. The analysis shows that, for any connected graph G, it holds that d(v,u) ≤ d_m(v,u) and dim(G) ≤ mdim(G).

Item Type:	Thesis (Masters)
Uncontrolled Keywords:	Dimensi Metrik, Jarak Monofonik, Simpul Perifera Metric Dimension, Monophonic Distance, Peripheral Vertex
Subjects:	Q Science Q Science > QA Mathematics Q Science > QA Mathematics > QA166 Graph theory
Divisions:	Faculty of Science and Data Analytics (SCIENTICS) > Mathematics > 44101-(S2) Master Thesis
Depositing User:	Tantri Tarisma
Date Deposited:	30 Jul 2025 06:20
Last Modified:	30 Jul 2025 06:20
URI:	http://repository.its.ac.id/id/eprint/123215

Actions (login required)

View Item