Perpustakaan Digital ITB

Tingkat ekspansi dalam graf berhingga dan terhubung dari suatu kumpulan simpul adalah bilangan bulat terkecil dari banyaknya sisi sehingga lingkungan di sekitar kumpulan simpul tersebut memiliki lebih dari setengah bobot seluruh graf. Penelitian ini bertujuan mencari batas atas untuk tingkat ekspansi tersebut yang hanya bergantung pada bentuk graf dan kumpulan simpul yang diperhatikan. Analisis pada nilai eigen dari operator Laplace pada graf digunakan sebagai alat utama dalam penelitian ini. Dua batas atas didapatkan dan salah satunya relatif dekat dengan tingkat ekspansi. Contoh untuk beberapa bentuk graf diberikan untuk melihat kedekatan batas atas dengan tingkat ekspansi. Studi ini merupakan penulisan ulang, elaborasi, serta simulasi atas bukti yang dikemukakan oleh Fan R.K. Chung et al. (1997) dan Grigor’yan (2019).