Dimensi Metrik Monofonik Nonlokal pada Graf Degree Splitting

Nugroho, R. Adrian Rahadimas (2024) Dimensi Metrik Monofonik Nonlokal pada Graf Degree Splitting. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5002201041-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2026. Download (6MB) | Request a copy

Abstract

Diberikan graf terhubung G = (V (G), E(G)) berordo n, himpunan terurut Mnl = {m′ 1 , m′ 2 , . . . , m′ k} ⊆ V (G), dan simpul v ∈ V (G). Representasi metrik monofonik dari v terhadap Mnl, mr(v | Mnl) adalah k−vektor (dm(v, m′ 1 ), dm(v, m′ 2 ), . . . , dm(v, m′ k )) . Jarak monofonik antara simpul v dan m′ i pada graf G, dm(v, m′ i ), adalah lintasan monofonik−(v, m′ i ) terpanjang dari simpul v ke simpul m′ i . Lintasan monofonik−(v, m′ i ) adalah lintasan dari simpul v ke simpul m′ i tanpa busur, dengan busur adalah sisi yang menghubungkan dua simpul yang tidak bertetangga dalam lintasan−(v, m′ i ). Himpunan Mnl disebut sebagai himpunan pembeda monofonik nonlokal untuk graf G jika mr(v | Mnl) ̸= mr(u | Mnl) untuk setiap simpul u dan v yang tidak bertetangga. Himpunan pembeda monofonik nonlokal Mnl dengan jumlah elemen minimal disebut basis monofonik nonlokal dari G. Kardinalitas basis monofonik nonlokal dari G disebut dimensi metrik monofonik nonlokal dari G, dinotasikan mdimnl(G). Graf degree splitting dari graf G, DS(G), adalah graf yang diperoleh dengan menambahkan simpul baru dan menghubungkannya ke himpunan simpul-simpul yang memiliki derajat yang sama, dengan syarat himpunan tersebut memiliki setidaknya dua simpul dan setiap himpunan simpul yang memiliki derajat yang sama hanya dihubungkan dengan satu simpul baru. Pada Tugas Akhir ini dianalisis dan ditentukan dimensi metrik monofonik nonlokal dari graf Pn, Cn, Kn, Sn, Kn,m, Wn, Fn, dan graf degree splitting tersebut. Hasil dari Tugas Akhir ini diperoleh : mdimnl(Pn) = 1 untuk n ≥ 3; mdimnl(Cn) = 2 untuk n ≥ 4; mdimnl(Sn) = n − 2 untuk n ≥ 3; mdimnl(Kn) = 0 untuk n ≥ 1; mdimnl(Kn,m) = (n − 1) + (m − 1) untuk n, m ≥ 2; mdimnl(Wn) = 2 untuk n ≥ 5; mdimnl(Fn) = 1 untuk n ≥ 4; mdimnl(DS(Pn)) = 2 untuk n ≥ 3; mdimnl(DS(Cn)) = 2 untuk n ≥ 4; mdimnl(DS(Sn)) = n − 1 untuk n ≥ 3; mdimnl(DS(Kn)) = 0 untuk n ≥ 1; mdimnl(DS(Kn,m)) = (n − 1) + (m − 1) jika n = m dan mdimnl(DS(Kn,m)) = (n − 1) + (m − 1) + 1 jika n ̸= m, untuk n, m ≥ 2; mdimnl(DS(Wn)) = 3 untuk n ≥ 5; mdimnl(DS(Fn)) = 2 untuk n ≥ 4.
==================================================================================================================================
Given a connected graph G = (V (G), E(G)) of order n, an ordered set Mnl = {m′ 1 , m′ 2 , . . . , m′ k} ⊆ V (G), and a vertex v ∈ V (G), the monophonic metric representation of v with respect to Mnl, mr(v | Mnl), is the k-vector (dm(v, m′ 1 ), dm(v, m′ 2 ), . . . , dm(v, m′ k )). The monophonic distance between the vertex v and m′ i in the graph G, dm(v, m′ i ), is the longest monophonic path from vertex v to vertex m′ i . A monophonic path (v, m′ i ) is a path from vertex v to vertex m′ i without chords, where a chord is an edge connecting two non-adjacent vertices in the path (v, m′ i ). The set Mnl is called a nonlocal monophonic resolving set for graph G if mr(v | Mnl) ̸= mr(u | Mnl) for every pair of non-adjacent vertices u and v. The nonlocal monophonic resolving set Mnl with the smallest number of elements is called the nonlocal monophonic basis of G. The cardinality of the nonlocal monophonic basis of G is called the nonlocal monophonic metric dimension of G, denoted as mdimnl(G). The degree splitting graph of a graph G, DS(G), is the graph obtained by adding new vertices and connecting them to the set of vertices with the same degree, provided that the set contains at least two vertices and each set of vertices with the same degree is connected to only one new vertex. This thesis analyzes and determines the nonlocal monophonic metric dimension of the graphs Pn, Cn, Kn, Sn, Kn,m, Wn, Fn, and their degree splitting graphs. The results of this thesis are obtained as follows: mdimnl(Pn) = 1 for n ≥ 3; mdimnl(Cn) = 2 for n ≥ 4; mdimnl(Sn) = n − 2 for n ≥ 3; mdimnl(Kn) = 0 for n ≥ 1; mdimnl(Kn,m) = (n − 1) + (m − 1) for n, m ≥ 2; mdimnl(Wn) = 2 for n ≥ 5; mdimnl(Fn) = 1 for n ≥ 4; mdimnl(DS(Pn)) = 2 for n ≥ 3; mdimnl(DS(Cn)) = 2 for n ≥ 4; mdimnl(DS(Sn)) = n − 1 for n ≥ 3; mdimnl(DS(Kn)) = 0 for n ≥ 1; mdimnl(DS(Kn,m)) = (n − 1) + (m − 1) if n = m and mdimnl(DS(Kn,m)) = (n−1) + (m−1) + 1 if n ̸= m, for n, m ≥ 2; mdimnl(DS(Wn)) = 3 for n ≥ 5; and mdimnl(DS(Fn)) = 2 for n ≥ 4

Item Type:	Thesis (Other)
Uncontrolled Keywords:	graf degree splitting, jarak monofonik, lintasan monofonik, himpunan, pembeda monofonik nonlokal, dimensi metrik monofonik nonlokal, degree splitting graph, monophonic distance, monophonic path, monophonic nonlocal resolving set, monophonic nonlocal metric dimension
Subjects:	Q Science > QA Mathematics > QA159 Algebra Q Science > QA Mathematics > QA166 Graph theory
Divisions:	Faculty of Science and Data Analytics (SCIENTICS) > Mathematics > 44201-(S1) Undergraduate Thesis
Depositing User:	R. Adrian Rahadimas Nugroho
Date Deposited:	28 Aug 2024 06:02
Last Modified:	28 Aug 2024 06:02
URI:	http://repository.its.ac.id/id/eprint/114846

Actions (login required)

View Item