Plenary speakers

Some recent developments on the generalized spectral characterizations of graphs

Wei Wang
Xi’an Jiaotong University (China)

Plenary Talk 1: 29 Oct – 8:45am

A long-standing open problem in spectral graph theory is: “Which graphs are determined by their spectra?” Tracing its origins to chemistry over 60 years ago, this problem is deeply connected to several central questions in the field, including the graph isomorphism problem and Kac’s famous query, “Can one hear the shape of a drum?”. Notably, proving that a specific graph is determined by its spectrum remains highly challenging.

We explore this problem within the framework of the generalized spectrum. A graph $G$ is said to be \emph{determined by its generalized spectrum} if any graph $H$ that is cospectral with $G$ and whose complement is also cospectral with the complement of $G$ must be isomorphic to $G$ . This talk will present recent findings on this topic, along with a discussion of open questions in the area.

From Threshold Graphs to Chain Graphs: Spectral Perspectives

Milica Andelic
Kuwait University (Kuwait)

Plenary Talk 2: 29 Oct – 2:00pm

Threshold graphs and chain graphs represent distinct classes of graphs that often arise as solutions to extremal problems in spectral graph theory. Notably, many results concerning threshold graphs within the class of connected graphs have analogues in the context of chain graphs, particularly in the class of connected bipartite graphs. In this regard, several contributions by Vilmar and his research group have inspired corresponding results for chain graphs. In this talk, we revisit Vilmar’s findings on eigenvalue location, main eigenvalues, and characteristic polynomials of threshold graphs, and present their extensions and analogues for chain graphs.

Doubly Stochastic Matrices and Modified Laplacian Matrices of Graphs

Enide Andrade
University of Aveiro (Portugal)

Plenary Talk 3: 30 Oct – 9:00am

We consider modified Laplacian matrices of graphs, where the modification consists of adding the identity matrix to the Laplacian matrix of a graph $G$ . This results in a positive definite matrix $\tilde{L}_G$ . The inverse of $\tilde{L}_G$ is a doubly stochastic matrix. The goal of this paper is to investigate this inverse matrix and how it depends on properties of the underlying graph $G$ . In particular, we introduce a general monotonicity property for the entries of the inverse, and derive a sharper version for the case of path graphs. We also establish a lower bound for the diagonal entries as a function of the distances between vertices. Furthermore, we present a simple and efficient algorithm for computing the inverse when the graph is a tree.

Eigenvalue location technique and the largest eigenvalue of graphs

Francesco Belardo
University of Naples (Italy)

Plenary Talk 4: 30 Oct – 2:30pm

The eigenvalue location (EL) is an algorithm based on matrix congruence and Sylvester’s Inertia Law, which is applied to real symmetric matrices and provides the number of eigenvalues that are greater than, equal to, or less than a provided input value $\lambda$ . When a suitable matrix is a graph matrix, then the algorithm can be executed on the graph itself. In the years, the EL has been specialised to several graph matrices and classes of graphs, including the Laplacian matrix of trees, the adjacency matrix of cographs, or others.

One of the most successful applications of the EL regards the comparison of the largest eigenvalue (index) of trees and the identification of graphs with a small spectral radius (Hoffman Program) for various graph matrices.

We survey some of these results and outline some ongoing research on this topic.

Local properties of the spectral radius, Perron vector in graphs, and related topics

Bo Ning
Nankai University (China)

Plenary Talk 5: 31 Oct – 9:00am

In 2002, Nikiforov proved that for an $n$ -vertex graph $G$ with clique number $\omega$ and edge number $m$ , its spectral radius $\lambda(G)$ satisfies $\lambda (G) \leq \sqrt{2(1 - 1/\omega) m}$ , which confirmed a conjecture implicitly suggested by Edwards and Elphick. In this paper, we prove a local version of spectral Tur\’an inequality, showing that $\lambda^2(G)\leq 2\sum_{e\in E(G)}\frac{c(e)-1}{c(e)}$ , where $c(e)$ is the order of the largest clique containing the edge $e$ in $G$ . We also characterize the extremal graphs. Furthermore, we prove that our theorem implies Nikiforov’s theorem and provide an example in which the difference of Nikiforov’s bound and ours is $\Omega (\sqrt{m})$ for some cases. Our second result explores local properties of the Perron vector of graphs. We disprove a conjecture of Gregory, asserting that for a connected $n$ -vertex graph $G$ with chromatic number $k\geq 2$ and an independent set $S$ , we have

$\sum_{v\in S} x_v^2 \leq \frac{1}{2} - \frac{k-2}{2\sqrt{(k-2)^2 + 4(k-1)(n-k+1)}},$

where $x_v$ is the component of the Perron vector of $G$ with respect to the vertex $v$ . A modified version of Gregory’s conjecture is proposed. Besides these results, we also give a brief survey on related topics, focusing on the works by Chinese graph theorists.

Eigenvalue sums

Gabriel Coutinho
Universidade Federal de Minas Gerais (Brazil)

Plenary Talk 6: 31 Oct – 2:30pm

In spectral graph theory, many central parameters can be expressed or bounded in terms of eigenvalue sums of the adjacency matrix. Semidefinite programming provides a natural convex framework for formulating and studying such inequalities among eigenvalues. In this talk, I will outline how eigenvalue sums can be encoded within semidefinite programs and discuss applications to several conjectures. As a case study, I will present a short proof of a conjecture due to Wocjan, Elphick, and Anekstein, and more importantly, I will describe recent progress on other open problems as well as directions for future research.