Perpustakaan Digital ITB

Misalkan ???? adalah graf dengan himpunan titik tak kosong ????(????) dan himpunan sisi ????(????). Misalkan ???????? adalah graf roda dengan satu titik pusat dan ???? titik luar. Himpunan ?????????(????) disebut sebagai himpunan independen-[1,2] dari ???? jika ?????????? tidak saling bertetangga dan ??????????(????)\???? bertetangga dengan setidaknya satu dan paling banyak dua titik di ????. Banyaknya anggota minimum yang dapat dipilih dari suatu himpunan independen-[1,2] disebut sebagai bilangan independen-[1,2] dari ????, yang dinotasikan dengan ????1,2(????). Misalkan terdapat dua graf terhubung ???? dan ????, graf kali sisir sisi atau graf comb sisi antara ???? dan ????, yang dinotasikan dengan ?????????????????, merupakan graf hasil operasi yang diperoleh dari satu salinan ???? dan sebanyak |????(????)| salinan dari graf ???? dengan sisi ke-???? dari ???? ditempelkan dengan sisi ???? di salinan ke-???? dari ????. Pada tugas akhir ini, akan dibahas mengenai karakteristik dari graf ???????? dan ????????????????? yang memiliki himpunan independen-[1,2], serta mengidentifikasi bilangan independen-[1,2] pada graf tersebut.