BILANGAN KETERHUBUNGAN TITIK PELANGI KUAT PADA GRAF

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<n-2. Perhatikan bahwa banyak titik internal P_n  adalah n-2. Pikirkan sebuah pewarnaan titik W pada P_n  sedemikian hingga semua titik internal P_n  mendapat warna berbeda dan warnai titik-titik terminal P_n  dengan salah satu warna titik internal. Jelas terhadap pewarnaan W lintasan P_n  terhubung titik pelangi kuat dengan (n-2) warna, sehingga srvc(P_n )=n-2. Dalam artikel ini, akan dibahas bilangan keterhubungan titik pelangi kuat pada graf komplet, graf roda, dan  graf lintasan. Graf komplet K_n  adalah satu-satunya kelas graf yang mencapai batas bawah srvc(G)  dan graf lintasan P_n  adalah satu-satunya kelas graf yang mencapai batas atas srvc(G).