The Rainbow Connection Number of Some Graph Classes
All graphs considered in this thesis are connected, finite, and simple. Let G = (V (G),E(G)) be a nontrivial connected graph and m be a positive integer. Let c : E(G) → {1,2,...,m} be an m−coloring of the edges of G. A path P in G is called a rainbow path, if no two edg...
Saved in:
| Main Author: | |
|---|---|
| Format: | Theses |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/22630 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Institut Teknologi Bandung |
| Language: | Indonesia |
| Summary: | All graphs considered in this thesis are connected, finite, and simple. Let G = (V (G),E(G)) be a nontrivial connected graph and m be a positive integer. Let c : E(G) → {1,2,...,m} be an m−coloring of the edges of G. A path P in G is called a rainbow path, if no two edges of P are colored the same. Let x and y be vertices in V (G), a rainbow path is called an x−y rainbow path, if x and y be the end vertices. The rainbow connection number of G, denoted by rc(G), is the minimum positive integer m so that every pair of vertices in V (G) is connected by one path in which no two edges of it are colored the same. In other words, for every two vertices x and y in V (G), there exists a rainbow x−y path. The distance between two vertices x and y in V (G), denoted by d(x,y), is the length of a shortest path between them in G. The diameter of G is the max{d(x,y)|x,y ∈ V (G)}. Let k be the size of G, Chartrand, Johns, McKeon and Zhang showed that diam(G) ≤ rc(G) ≤ k. In this thesis we introduce new four graphs classes that are (Cm,Kn) flower graphs, flower (Wm,Kn) graphs, (Cm,Fn) flower graphs, and lemon graphs. Then, we determine the rainbow connection number of them. |
|---|