Perpustakaan Digital ITB

Misalkan G graf sederhana dengan himpunan titik dan sisi masing-masing V (G) dan E(G). Misalkan W V (G). Himpunan W dikatakan sebagai himpunan independen-[1,2] dari G jika setiap dua titik berbeda dalam W tidak saling bertetangga, dan setiap titik v 2 V (G) ????W bertetangga dengan tepat satu atau dua titik diW. Kardinalitas minimum dari semua himpunan independen-[1,2] dari G disebut bilangan independen-[1,2] dari G. Untuk dua graf terhubung G dan H, hasil kali sisir antara G dan H di suatu titik o 2 V (H), dinotasikan dengan G .o H, adalah graf yang diperoleh dari [V (G)] kopian H dan satu kopian G, kemudian mengidentifikasi kopian ke-i dari H di titik o pada titik ke-i dari G. Dalam tugas akhir ini, semua sifat dari G dan H sedemikian rupa sehingga G .o H memiliki himpunan independen-[1,2], ditunjukkan. Selanjutnya, nilai eksak dari bilangan independen- [1,2] G.oH dengan G adalah sembarang graf terhubung dan H adalah graf lengkap, graf bintang, atau graf bipartit lengkap, juga ditentukan.