Kompleksitas Graf Cocktail Party dan Graf Sandat Berdasarkan Spektrum Laplacian

Fransiskus Fran (Universitas Tanjungpura)
Suryani Suryani (Universitas Tanjungpura)
Bayu Prihandono (Universitas Tanjungpura)

Pythagoras: Jurnal Matematika dan Pendidikan Matematika
Vol. 21 No. 1 (2026)

Misalkan adalah graf terhubung dan tidak berarah. Setiap graf terhubung memiliki pohon perentang, yaitu subgraf yang terdiri dari seluruh simpul dalam graf dan membentuk pohon. Kompleksitas graf , yang dinotasikan dengan , merupakan banyaknya pohon perentang pada graf . Dalam artikel ini, digunakan pendekatan spektrum Laplacian untuk menentukan kompleksitas graf, khususnya graf Cocktail Party dan graf Sandat. Spektrum Laplacian merupakan matriks yang dibentuk dari susunan nilai eigen matriks Laplacian dan multiplisitasnya. Penelitian diawali dengan menentukan matriks adjacency dan matriks degree dari graf Cocktail Party untuk dan graf Sandat untuk , kemudian dibentuk matriks Laplacian serta polinomial karakteristik matriks Laplaciannya. Selanjutnya, dirumuskan formula polinomial karakteristik ke- matriks Laplacian masing-masing graf. Pembuktian kebenaran formula polinomial karakteristik dilakukan dengan memanfaatkan matriks blok. Berdasarkan hasil tersebut, dirumuskan dan dibuktikan formula spektrum Laplacian, serta formula kompleksitas graf untuk graf Cocktail Party dan Sandat. Hasil dari penelitian ini adalah rumusan spektrum Laplacian dan kompleksitas dari graf Cocktail Party serta graf Sandat.