THE RAINBOW VERTEX CONNECTION NUMBER OF FINGER GRAPHS, MOUNTAIN GRAPHS, AND BOAT GRAPHS
All graphs considered in this thesis are simple and finite. Let G = (V (G),E(G)) be a nontrivial connected graph and k be a positive integer. Let c : V (G) → {1,2,...,k} be a k−coloring of the vertices of G. A path of G is said a rainbow vertex-path if whose internal ve...
Saved in:
| Main Author: | |
|---|---|
| Format: | Theses |
| Language: | Indonesia |
| Online Access: | https://digilib.itb.ac.id/gdl/view/20232 |
| 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 simple and finite. Let G = (V (G),E(G)) be a nontrivial connected graph and k be a positive integer. Let c : V (G) → {1,2,...,k} be a k−coloring of the vertices of G. A path of G is said a rainbow vertex-path if whose internal vertices have distinct colors. A vertex-colored graph is said rainbow vertex-connected if for any two vertices are connected by at least one rainbow vertex-path. The rainbow vertex-connection number of a connected graph, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex-connected. Let n be the order of G, Krivelevich and Yuster showed that diam(G)−1 ≤ rvc(G) ≤ n−2. If G consists of q cut vertices, then rvc(G) ≥ q. In this thesis we define and determine the rainbow vertex-connection number of three new graph classes, namely finger graphs, mountain graphs, and boat graphs. |
|---|