On normalized Laplacian spectrum of some special graphs

Abstract

Spektral çizge teorisi, bir çizgenin yapısı ve çizgeye ait herhangi bir matrisin özdeğerleri arasındaki ilişkiyi inceler. Birçok ilginç çizge, çizgenin bazı özel matrisleri ile ilişkili özdeğerlerin belirlenmesine yardımcı olabilen zengin bir yapıya sahiptir. İki düğümün ardışık olması durumuna göre elemanları belirlenen bitişiklik matrisi A dahil, Laplacian matris ? ve normalize Laplacian matris ? ? gibi pek çok farklı matris vardır. ?, ayrık bir düğümü bulunmayan yönsüz bir çizge olsun. Bu durumda D, bu çizgedeki düğümlerin derecelerini içeren köşegen matris olmak üzere, normalize Laplacian matrisi ? ?(?) = D^((-1)/2) ?(?) D^((-1)/2) olarak tanımlanır. ? ?(?) matrisinin özdeğerleri, çizgenin normalize Laplacian özdeğerleri olarak adlandırılır. Cavers [Cavers, 2010]'de, normalize Laplacian özdeğerleri ile ilgili olarak ko-spektral olan çizgelere odaklanmıştır. Ayrıca, birkaç normalize Laplacian özdeğeri ile çizgelerin özelliklerini tartışmıştır. Aynı zamanda Cavers ve Fallat [Cavers et al., 2010]'de, ? ?(?) enerji adı verilen normalize Laplacian özdeğerleri ile ilgili basit bir çizgenin enerjisi üzerinde durmuştur. Van Dam ve Omidi [Dam and Omidi, 2011]'te, normalize Laplacian'ın üç farklı özdeğerine sahip olan bu çizgelerin bir kombinatoryal karakterizasyonunu vermiştir. Bu tezin amacı, bazı özel çizgelerin, normalize Laplacian spektrumunu araştırmaktır. Özellikle [Hakimi-Nezhaad and Ghorbani, 2017] içeriğinden faydalanarak, bazı birleşik çizge türleri için, özdeğerlerin nasıl hesaplanabileceğini anlamaya çalışacağız.

Spectral graph theory looks at the interplay between the structure of a graph and the eigenvalues of a matrix associated with the graph. Many interesting graphs have rich structure which can help in determining eigenvalues associated with some particular matrix of a graph. There are many different matrices that are considered, including the adjacency matrix A whose entries indicate when two vertices are adjacent, Laplacian matrix ? and normalized Laplacian matrix ? ?. Let ? be an undirected graph without an isolated vertex, then the normalized Laplacian matrix ? ?(?) is defined as ? ?(?) = D^((-1)/2) ?(?) D^((-1)/2) where D is diagonal matrix whose entries are degrees of vertices of ?. The eigenvalues of ? ?(?) are called as the normalized Laplacian eigenvalues of ?. Cavers in [Cavers, 2010] focused on graphs that are co-spectral with respect to the normalized Laplacian eigenvalues. Furthermore, he discussed properties of graphs with few normalized Laplacian eigenvalues. Almost at the same time, he and Fallat [Cavers et al., 2010] considered the energy of a simple graph with respect to its normalized Laplacian eigenvalues, which is called the ? ?-energy. Van Dam and Omidi in [Dam and Omidi, 2011] gave a combinatorial characterization of those graphs whose normalized Laplacian have three distinct eigenvalues. The goal of this thesis is to investigate the spectrum of the normalized Laplacian of some special graphs, in particular, we will be looking at understanding how eigenvalues can be computed for some types of join graphs, as a note on [Hakimi-Nezhaad and Ghorbani, 2017].