Groupe d’études et de recherche en analyse des décisions

On Laplacian eigenvalues of graph

Kinkar Chandra Das Sungkyunkwan University, Corée, République de

Spectral graph theory studies connections between combinatorial properties of graphs and the eigenvalues of matrices associated to the graph, such as the adjacency matrix, the Laplacian matrix and the signless Laplacian matrix. Let \(G = (V; E)\) be a simple graph. Denote by \(D(G)\) the diagonal matrix of its vertex degrees and by \(A(G)\) its adjacency matrix. Then the Laplacian matrix of \(G\) is \(L(G) = D(G)- A(G)\). Denote the spectrum of \(L(G)\) by \(S(L(G)) = (\mu_1, \mu_2, ..., \mu_n)\), where we assume the eigenvalues to be arranged in nonincreasing order: \(\mu_1 \geq \mu_2 \geq \cdots \geq \mu_{n-1} \geq \mu_n = 0\). Let \(a\) be the algebraic connectivity of graph \(G\). Then \(a = \mu_{n-1}\). Among all eigenvalues of the Laplacian matrix of a graph, the most studied is the second smallest, called the algebraic connectivity \((a(G))\) of a graph. In this talk we discuss some properties on \(\mu_1(G)\) and \(a(G)\) of graph \(G\). We obtain some integer and real Laplacian (adjacency, signless Laplacian) eigenvalues of graphs. Moreover, we discuss several relations between eigenvalues (adjacency, Laplacian, signless Laplacian) and graph parameters. Finally, we give some conjectures on the spectral graph theory.


Entrée gratuite.
Bienvenue à tous!