Retour aux activités
Séminaire Fondation HEC Montréal

On Laplacian eigenvalues of graph

iCalendar

9 fév. 2017   10h45 — 12h00

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!

Pierre Hansen responsable

Lieu

Salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour Montréal QC H3T 1J4 Canada

Organismes associés

Chaire d'exploitation des données

GERAD

Axe de recherche

Applications de recherche