RAINBOW 2-CONNECTION NUMBER OF SOME GRAPH CLASSES

• Main Author: Hayat Susanti, Bety
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/45890
• Institution: Institut Teknologi Bandung

The concept of rainbow connection number was introduced by Chartrand et al. which was then generalized by the concept of rainbow k-connectivity of a finite and ?-connected graph. The rainbow k-connection number of a graph G, denoted by rck(G), is defined as the minimum integer j for which there exists a j-edge-coloring of G such that for any two distinct vertices u and v of G, there exist at least k internally disjoint u – v rainbow paths. By coloring the edges of G with distinct colors, we see that every two vertices of G are connected by k internally disjoint rainbow paths and so rck(G) is defined for every integer k with 1 ? k ? ?. Determination of rainbow k-connection numbers of any graph is not easy, even for k = 1. It has been proven that the problem is NP-complete. Therefore, some researchers are trying to determine rainbow k-connection numbers for particular classes of graphs. This dissertation is focused on the determination of rainbow 2-connection numbers of some 2-connected graphs and their subdivision, and the rainbow 2-connectivity of graphs resulted from graph operations including path amalgamation, edge-comb product, Cartesian product, and strong product.