KONEKTIVITAS-TITIK HASIL KALI KRONECKER DUA GRAF

Abstract

Misalkan dan dua buah graf. Hasil kali kronecker dan , dilambangkan dengan , adalah graf dengan himpunan titik dan himpunan sisi dan . Konektivitas-titik graf atau adalah minimum banyaknya titik yang harus dihapus agar graf yang baru tak terhubung atau graf trivial. Konektivitas-titik super dari graf , dilambangkan dengan , adalah minimum banyak titik yang dihapus agar graf yang baru tak terhubung dan tidak memuat titik terasing. Jelas bahwa jika graf tak terhubung, maka . Penentuan nilai eksak konektivitas-titik dan konektivitas-titik super hasil kali kronecker dua graf secara umum merupakan permasalahan yang sulit. Dalam artikel ini akan ditunjukkan bahwa , jika dan . Begitu juga, akan ditunjukan , jika graf bipartit dengan dan . Dan ditunjukan juga bahwa , jika dan . Akhirnya, dibuktikan bahwa , jika , , dan . Pembahasan ini akan diawali dengan pembuktian bahwa perkalian kronecker dua graf terhubung merupakan graf terhubung jika dan hanya jika salah satu dari kedua graf tersebut memuat sikel ganjil.

Kata Kunci: konektivitas-titik hasil kali kronecker dua graf, konektivitas-titik super hasil kali kronecker dua graf untuk

beberapa kelas graf tertentu.