Perpustakaan Digital ITB

Misalkan ???? graf sederhana dengan himpunan titik dan sisi masing-masing ????(????) dan ????(????). Misalkan ?????????(????). Himpunan W dikatakan sebagai himpunan independen-[1,2] dari ???? jika setiap dua titik berbeda dalam ???? tidak saling bertetangga, dan setiap titik ?????????(????)????? bertetangga dengan tepat satu atau dua titik di ????. Kardinalitas minimum dari semua himpunan-[1,2] dari ???? disebut bilangan independen-[1,2] dari ????. Untuk dua graf terhubung ???? dan ????, graf comb sisi antara ???? dan ???? di suatu sisi ?????????(????), dinotasikan dengan ????????????? adalah graf yang diperoleh dari |????(????| kopian ???? dan satu kopian ????, kemudian mengidentifikasi di sisi ???? untuk kopian ke-i dari ???? pada sisi ke-???? dari ????. Dalam tugas akhir ini, beberapa graf sederhana yang memiliki himpunan independen-[1,2], ditunjukkan. Kemudian untuk ????,???????? graf lengkap, dan ????????,???? graf bipartit lengkap sedemikian rupa sehingga ????????????????? dan ?????????????????,???? memiliki himpunan independen-[1,2],juga ditunjukkan. Selanjutnya nilai eksak dari bilangan independen-[1,2] untuk ????,????????, dan ????????,???? sedemikian rupa sehingga ????????????????? dan ?????????????????,???? memiliki himpunan independen-[1,2] juga ditentukan.