Bilangan Kromatik Lokasi Jarak Dua Pada Graf Hasil Operasi Produk Tensor Dua Graf Well Known

Zain, Neni Nur Laili Ersela (2024) Bilangan Kromatik Lokasi Jarak Dua Pada Graf Hasil Operasi Produk Tensor Dua Graf Well Known. Masters thesis, Institut Teknologi Sepuluh Nopember.

Text 6002221001-Master_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 March 2026. Download (3MB) | Request a copy

Abstract

Pewarnaan simpul jarak dua adalah pewarnaan ϕ2 : V (G) → {1, 2, ..., k} sedemikian rupa sehingga terdapat dua simpul u dan v dengan d(u, v) ≤ 2 berakibat ϕ2(u) ̸= ϕ2(v). χ2(G) menyatakan minimum k, sehingga graf G mempunyai k-pewarnaan jarak dua. Misalkan c adalah k-pewarnaan dari k-pewarnaan jarak dua dan Π2 = {C1, C2, ..., Ck} merupakan partisi dari V (G) ke dalam kelas-kelas warna yang dihasilkan. Untuk setiap v ∈ V (G), kode warna dari v terhadap Π2 didefinisikan sebagai k-vektor : cΠ2 (v) = (d(v, C1), d(v, C2), ..., d(v, Ck)), dimana d(v, Ci) = min{d(v, x) : x ∈ Ci} untuk 1 ≤ i ≤ k. Jika setiap simpul di G punya kode warna yang berbeda terhadap Π2, maka c disebut pewarnaan lokasi jarak dua dari G. Pada tesis ini fokus pengerjaan dilakukan pada graf hasil operasi produk tensor. Operasi tensor (tensor product) dua graf G1 dan G2 dinotasikan dengan G = G1 ⊗ G2 dimana dua buah simpul dalam V pada graf G yaitu (u1, u2) dan (v1, v2) akan bertetangga jika u1v1 ∈ E(G1) dan u2v2 ∈ E(G2), dengan kata lain dG1 (u1, v1) = 1 dan dG2 (u2, v2) = 1. Modifikasi Algoritma Greedy dan DSatur digunakan untuk menentukan pola pewarnaan jarak dua dan pewarnaan lokasi jarak dua pada graf. Hasil penelitian ini didapatkan beberapa teorema mengenai bilangan kromatik jarak dua dan bilangan kromatik lokasi jarak dua pada graf hasil operasi produk tensor antara dua graf well known untuk Pm ⊗ Kn, Cm ⊗ Kn, Km ⊗ Kn dan Sm ⊗ Kn.
========================================================================================================================
The 2-distance k-coloring is coloring ϕ2 : V (G) → {1, 2, ..., k} such that there are two vertices u and v with d(u, v) ≤ 2 caused ϕ2(u) ̸= ϕ2(v). χ2(G) represents the minimum of k, so that graph G has 2-distance k-coloring. Let c be the k-coloring of 2-distance k-coloring and Π2 = {C1, C2, ..., Ck} be the partition of V (G) into the resulting color classes. For each v ∈ V (G), the color code of v with respect to Π2 is defined as a k-vector : cΠ2 (v) = (d(v, C1), d(v, C2), ..., d(v, Ck)), where d(v, Ci) = min{d(v, x) : x ∈ Ci} for 1 ≤ i ≤ k. If each vertex in G has a different color code relative to Π2, then c is called a 2-distance locating coloring from G. In this thesis the focus of work is on graphs resulting from product tensor operations. The tensor operation (tensor product) of two graphs G1 and G2 is denoted by G = G1⊗G2 where two vertices in V in graph G, namely (u1, u2) and (v1, v2) will be neighbors if u1v1 ∈ E(G1) and u2v2 ∈ E(G2), in other words dG1 (u1, v1) = 1 and dG2 (u2, v2) = 1. Greedy and DSatur algorithm modifications are used to determine the two-distance coloring pattern and the two-distance location coloring on the graph. As a result of this research, several theorems were obtained regarding 2-distance chromatic numbers and 2-distance locating chromatic number on graphs resulting from tensor product operations, there are Pm ⊗ Kn, Cm ⊗ Kn, Km ⊗ Kn and Sm ⊗ Kn.

Item Type:	Thesis (Masters)
Uncontrolled Keywords:	Tensor Product, Greedy and DSatur Algorithm Modification, 2-Distance Chromatic Number, 2-Distance Locating Chromatic Number, Operasi Produk Tensor, Modifikasi Algoritma Greedy dan DSatur, Bilangan Kromatik Jarak Dua, Bilangan Kromatik Lokasi Jarak Dua.
Subjects:	Q Science > QA Mathematics > QA166 Graph theory
Divisions:	Faculty of Science and Data Analytics (SCIENTICS) > Mathematics > 44101-(S2) Master Thesis
Depositing User:	Neni Nur Laili Ersela Zain
Date Deposited:	13 Feb 2024 14:57
Last Modified:	13 Feb 2024 14:57
URI:	http://repository.its.ac.id/id/eprint/106709

Actions (login required)

View Item