Kompleksitas Graf Cocktail Party dan Graf Sandat Berdasarkan Spektrum Laplacian

Abstract

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.