Spektrum Laplace Graf Mahkota dan Graf Benteng
DOI:
https://doi.org/10.21831/pythagoras.v19i1.60818Keywords:
graf mahkota, graf benteng, polinomial karakteristik, matriks laplace, spektrum laplaceAbstract
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 K2 dan graf Lengkap Kn. Sementara itu graf Benteng Bnn adalah graf yang diperoleh dari hasil perkalian kartesian dua buah graf Lengkap Kn. Hasil penelitian telah diperoleh polinomial karakteristik dari matriks Laplace untuk graf Mahkota dengan n>=3 dan graf Benteng Bnn 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 K2 and Kn. Meanwhile, rook graph is a graph obtained from the cartesian product of two complete graph Kn. 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.
References
Aldous, J. M., & Wilson, R. J. (2004). Graphs and Applications An Introductory Approach. Great Britian: Springer.
Arumugam, S., Brandstädt, A., and Nishizekii, T. (2016). Handbook of Graph Theory, Combinatorial Optimization, and Algorithms. New York: CRC Press.
Biggs, N. (1993). Algebraic Graph Theory. New York: Cambridge University Press.
Das, K.C. (2004). The Laplacian Spectrum of a Graph. Computers and Mathematics with Applications 48 (2004) 715-724. https://doi.org/10.1016/j.camwa.2004.05.005
Das, K.C., and Mojallal, S.A. (2014). On Laplacian Energy of Graphs. Discrete Math, 325(1), 52-64. https://doi.org/10.1016/j.disc.2014.02.017
Deng A., Kelmans A., Juan Meng. (2013). Laplacian spectra of regular graph transformations. Discrete Applied Mathematics, Volume 161, Issues 1–2, (18-133). https://doi.org/10.1016/j.dam.2012.08.020
Du, Z., and Zhou, B. (2012). Upper Bounds for The Sum of Laplacian Eigenvalues of Graphs. Linear Algebra Appl, 436(9), 3672-3683. https://doi.org/10.1016/j.laa.2012.01.007
Fiedler, M. (1973). Algebraic Connectivity of Graphs. Accessed: March 7, 2023. [Online]. http://dml.cz/dmlcz/101168
Insani, N., & Waryanto, N. H. (2012). Penerapan Teori Graf pada Analisi Jejaring Sosial dengan Menggunakan Microsoft Nodexl. Pythagoras, 7(1), 83-100. http://dx.doi.org/10.21831/pg.v7i1.2839
Melly Amaliyanah, Siti Rahmah Nurshiami, Triyani Triyani. (2022). Spektrum Laplace pada Graf Kincir
Angin Berarah Q_k^3. Majalah Ilmiah Matematika dan Statistika, 22(2), 131-144. https://doi.org/10.19184/mims.v22i2.31128
Munir, R. (2016). Matematika Diskrit Edisi 6. Penerbit Informatika: Bandung.
Orden, D., Guzman, J. M., Maestre, I. M., & Hoz, E. D. (2017). Spectrum Graph Coloring and Applications to WiFi Channel Assigment. Symmetry, 10(3), 65-92. https://doi.org/10.3390/sym10030065
Runtunuwu, Y. I., Mananohas, M. L., & Montolalu, C. E. (2021). Derajat Laplacian dari Graf Lengkap, Graf Bipartisi Komplit, Graf Matahari dan Graf yang memiliki n-1 Derajat berbeda. d'CARTESIAN: Jurnal Matematika dan Aplikasi, 10(1), 15-23. https://ejournal.unsrat.ac.id/index.php/decartesian/article/view/32698
Selvia, S. M., Narwen, & Zulakmal. (2019). Spektrum Graf Bintang S_n dan Graf Lengkap K_n Untuk n≥2. Jurnal Matematika UNAND, 4(4), 129-136. https://doi.org/10.25077/jmu.4.4.129-136.2015
Yahya, A., & Soeharyadi, Y. (2020). Spektrum Operator Laplace Diskret pada graf Torus. Jurnal Riset dan Aplikasi Matematika, 4(1), 35-49. https://doi.org/10.26740/jram.v4n1.p35-49
Additional Files
Published
How to Cite
Issue
Section
License
Pythagoras is licensed under a Creative Commons Attribution 4.0 International License.
Based on a work at http://journal.uny.ac.id/index.php/pythagoras.
