Spektrum Laplace Graf Mahkota dan Graf Benteng

Abstract

Spektrum dari suatu graf adalah susunan nilai eigen dari matriks ketetanggaan graf beserta multiplisitasnya. Spektrum graf yang dihasilkan dari matriks Laplace disebut spektrum Laplace. Matriks Laplace dari graf diperoleh dari selisih matriks ketetangaan graf dengan matriks diagonal dimana elemen-elemen diagonal utamanya merupakan derajat simpul dari graf. Penelitian ini mengkaji bentuk spektrum Laplace dari graf Mahkota dan graf Benteng. Graf Mahkota adalah graf yang diperoleh dari komplemen hasil perkalian kartesian graf Lengkap K₂ dan graf Lengkap K_n. Sementara itu graf Benteng B_nn adalah graf yang diperoleh dari hasil perkalian kartesian dua buah graf Lengkap K_n. Hasil penelitian telah diperoleh polinomial karakteristik dari matriks Laplace untuk graf Mahkota dengan n>=3 dan graf Benteng B_nn dengan n>=2. Lebih lanjut spektrum Laplace dari kedua graf juga telah diperoleh.

The spectrum on a graph is a set of eigenvalues of the adjacency matrix along with their multiplicities. The spectrum of a Laplace matrix is called the Laplace spectrum. The Laplace matrix of a graph is obtained from the difference between a adjacency matrix and a diagonal matrix where the elemens of main diagonal are the vertices degree of the graph. This research studied the Laplace spectrum on the crown graph and the rook graph.  A crown graph is a graph obtained from the complement of the cartesian product of complete graph K₂ and K_n. Meanwhile, rook graph is a graph obtained from the cartesian product of two complete graph K_n. The results of study are formula of the characteristic polynomial of Laplace matrix for the crown graph with n>=3 and the rook graph with n>=2. Furthermore, the Laplace spectrum of both graphs has also been obtained.