BILANGAN KETERHUBUNGAN TITIK PELANGI KUAT PADA GRAF

STRONG RAINBOW VERTEX-CONNECTION OF GRAPH

Graf G dikatakan terhubung titik pelangi jika setiap dua titik di G dihubungkan oleh suatu lintasan yang titik-titik internalnya memiliki warna yang berbeda, lintasan seperti itu disebut lintasan pelangi. Bilangan keterhubungan titik pelangi dari graf terhubung G, dilambangkan dengan rvc(G)  merupakan banyaknya warna terkecil yang diperlukan untuk membuat G terhubung titik pelangi. Graf G dikatakan terhubungan titik pelangi kuat jika untuk setiap dua titik u dan v berbeda di G ada sebuah lintasan pelangi terpendek antara u dan v, dilambangkan dengan srvc(G). Amati bahwa rvc(G)≤srvc(G) untuk sembarang graf terhubung tak trivial G. Jika G graf terhubung dengan n titik dan n≥3, maka 0≤srvc(G)≤n-2. Lebih jauh, batas-batas ini “tajam”. Misalkan n≥4 dengan diam(G)=1, maka G=K_n  sehingga srvc(G)=0

A graph G is said to be rainbow vertex connected if every two vertices in G are connected by a path whose internal vertices have different colors, such a path is called a rainbow path. The rainbow vertex connectedness number of connected graph G, denoted by rvc(G) is the smallest number of colors needed to make G rainbow vertex connected. A graph G is said to be strongly rainbow-connected if for every two distinct vertices u and v in G there is a shortest rainbow path between u and v, denoted by srvc(G). Observe that rvc(G)≤srvc(G) for any nontrivially connected graph G. If G graph is connected with n vertices and n≥3, then 0≤srvc(G)≤n-2. Furthermore, these boundaries are "sharp". Suppose n≥4 with diam(G)=1, then G=K_n   so that srvc(G)=0