DIMENSI PARTISI DAN DIMENSI PARTISI BINTANG GRAF HASIL OPERASI COMB DUA GRAF TERHUBUNG

ALFARISI, RIDHO (2017) DIMENSI PARTISI DAN DIMENSI PARTISI BINTANG GRAF HASIL OPERASI COMB DUA GRAF TERHUBUNG. Masters thesis, Institut Teknologi Sepuluh Nopember.

[img]
Preview
Text
1215201001-Master_Theses.pdf - Published Version

Download (1MB) | Preview

Abstract

Misalkan $G$ adalah sebuah graf nontrivial dan terhubung dengan himpunan simpul $V(G)$, himpunan sisi $E(G)$ dan $S\subseteq V(G)$ dengan simpul $v\in V(G)$, jarak antara $v$ dan $S$ adalah $d(v,S)=$min$\{d(v,x)|x\in S\}$. Untuk sebuah partisi $\Pi=\{S_1,S_2,S_3,...,S_k\}$ dari $V(G)$, representasi simpul $v$ terhadap $\Pi$ didefinisikan oleh pasangan $r(v|\Pi)=(d(v,S_1),d(v,S_2),...,d(v,S_k))$. Partisi $\Pi$ disebut partisi pembeda dari $G$ jika semua representasi dari setiap simpul $v\in V(G)$ berdeda. Kardinalitas minimum dari partisi pembeda disebut dimensi partisi dari $G$ dan dinotasikan sebagai pd($G$). Ragam lain dari konsep dimensi partisi yaitu dimensi partisi bintang. Misalkan $\Pi=\{S_1,S_2,S_3,...,S_k\}$ disebut partisi pembeda bintang jika setiap kelas-kelas partisi $S_i, 1\leq i\leq k$ menginduksi sebuah graf bintang di $G$ dan semua representasi dari setiap simpul $v\in V(G)$ berdeda. Kardinalitas minimum dari partisi pembeda bintang disebut dimensi partisi bintang dari $G$ dan dinotasikan sebagai spd($G$). Dalam Penelitian ini, kami akan menentukan dimensi partisi dan dimensi partisi bintang dari graf hasil operasi produk $comb$. Operasi $comb$ dinotasikan $\triangleright$. Untuk graf $G$ dan $H$, graf hasil operasi $comb$ $G\triangleright H$ didefinisikan sebagai graf yang diperoleh dengan mengambil satu duplikat $G$ dan $|G|$ duplikat dari $H$ dan melekatkan simpul $u$ dari masing masing graf $H$ duplikat ke-$i$ pada simpul ke-$i$ dari graf $G$. Misalkan $G$ dan $H$ adalah graf terhubung meliputi lintasan, lingkaran, dan graf lengkap. ========================================================================================================== Let $G$ be a nontrivial and connected graphs with vertex set $V(G)$, edge set $E(G)$ and $S\subseteq V(G)$ with vertex $v\in V(G)$. The distance between $v$ and $S$ is $d(v,S)=$min$\{d(v,x)\}$ for $x\in S$. For an ordered partition $\Pi=\{S_1,S_2,S_3,...,S_k\}$ of vertex set $V(G)$, the representation of $v$ with respect to $\Pi$ is defined by the ordered $r(v|\Pi)=(d(v,S_1),d(v,S_2),...,d(v,S_k))$. The minimum cardinality of resolving partition is partition dimension of $G$, denoted by pd($G$). A variant of partition dimension concept called star partition dimension of a graph. Let $\Pi = \{S_1,S_2,S_3,...,S_k\}$ be a star resolving partition for $G$ if each partition class $S_i, \,1\leq i\leq k$, induces a star in $G$ and all representation of vertices $v\in V(G)$ are unique. The minimum cardinality of resolving partition is a star partition dimension of $G$, denoted by spd($G$). In this research, we determine the partition dimension and star partition dimension of comb product of graphs. For graphs $G$ and $H$, the comb product $G\triangleright H$ is defined as the graph obtained by taking one copy of $G$ and $|V(G)|$ copies of $H$ and grafting the $i$-th copy of $H$ at the vertex $o$ to the $i$-th vertex of $G$. In this work $G$ and $H$ are restricted to path, cycle and complete graph.

Item Type: Thesis (Masters)
Uncontrolled Keywords: Partisi pembeda, partisi pembeda bintang, dimensi partisi, dimensi partisi bintang, operasi comb, Resolving partition, star resolving partition, partition dimension, star partition dimension
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Mathematics and Science > Mathematics > (S2) Master Theses
Depositing User: Ridho Alfarisi Alfarisi
Date Deposited: 23 Feb 2017 03:02
Last Modified: 23 Feb 2017 03:04
URI: http://repository.its.ac.id/id/eprint/1841

Actions (login required)

View Item View Item