Keterhubungan pelangi dan keterhubungan pelangi kuat pada konstruksi graf M-splitting = Rainbow connection and rainbow connection number on the graph construction M-splitting / Fendy Septyanto
| Main Authors: | Fendy Septyanto, author, Add author: Kiki Ariyanti Sugeng, supervisor, Add author: Djati Kerami, examiner, Add author: Hengki Tasman, examiner, Add author: Hendri Murfi, examiner |
|---|---|
| Format: | Masters Doctoral |
| Terbitan: |
Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia
, 2016
|
| Subjects: | |
| Online Access: |
http://lontar.ui.ac.id/detail?id=20433838 |
Daftar Isi:
- Bilangan keterhubungan pelangi dari suatu graf G, disimbolkan rc(G), adalah banyaknya warna minimal yang diperlukan untuk mewarnai busur-busur di G sedemikian rupa sehingga setiap pasang simpul dapat dihubungkan oleh suatu lintasan yang warnanya berbeda semua. Bilangan keterhubungan pelangi kuat dari suatu graf G, disimbolkan src(G), adalah banyaknya warna minimal yang diperlukan untuk mewarnai busur-busur di G sedemikian rupa sehingga setiap pasang simpul dapat dihubungkan oleh suatu geodesik (lintasan terpendek) yang warnanya berbeda semua. Diberikan suatu graf H dan suatu bilangan asli m, sebuah graf baru yang disebut m-splitting dari H dibentuk dengan memunculkan m simpul baru ("kloning") dari masing-masing simpul di H, kemudian memunculkan satu busur baru yang menghubungkan setiap simpul kloning dengan setiap tetangga di H dari simpul aslinya. Tesis ini meliputi hasil kajian tentang rc dan src pada hasil konstruksi m-splitting dari graf secara umum maupun dari beberapa kelas graf. ......The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of colors needed to color the edges of G such that every pair of vertices is connected by a path consisting of different colors. The strong rainbow connection number of a graph G, denoted by src(G), is the smallest number of colors needed to color the edges of G such that every pair of vertices is connected by a geodesic (shortest path) consisting of different colors. Given a graph H and a natural number m, a new graph called the m-splitting of H is formed by creating m new vertices (?clones?) from each vertex of H, and then forming a new edge connecting each cloned vertex to each neighbor of the original vertex; the new graph is denoted by Splm(H). This thesis contains some results regarding the rc and src of the m-splitting of arbitrary graph in general, and particularly of some specific classes of graph.