RAINBOW 2-CONNECTION NUMBER OF SOME GRAPH CLASSES
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 exis...
Saved in:
| Main Author: | |
|---|---|
| Format: | Dissertations |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/45890 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | 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.
|
|---|