<![CDATA[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).]]>
Copyrights © 2022
