Eigenvalue sums
Gabriel Coutinho
Universidade Federal de Minas Gerais (Brazil)
Plenary Talk 1: 29 Oct – 8:45am
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.
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.
The Brualdi-Hoffman-Turán-type problem and Triangles
Zhenzhen Lou
University of Shanghai for Science and Technology (China)
Plenary Talk 3: 29 Oct – 4:50pm
The Brualdi-Hoffman-Turán-type problem presents a fascinating inquiry: among all graphs with
edges that exclude a specific graph
, what is the maximum possible value of the spectral radius? This problem bears a close connection to Mantel’s theorem. In 1970, Nosal established a spectral counterpart, demonstrating that for every triangle-free graph
with
edges, the spectral radius
. The first result regarding non-bipartite triangle-free graphs was put forward by Lin, Ning, and Wu [Combin. Probab. Comput. 30 (2021)]. Subsequently, Li, Feng, and Peng [Electron. J. Combin. 31 (2024)] characterized the extremal non-bipartite triangle-free graphs with the maximal spectral radius in the case where the number of edges
is even. Additionally, they posed the following question: For non-bipartite graphs that are free of all odd cycles
and have an even number of edges
, what is the extremal graph with the maximal spectral radius? This question is fully resolved in the present talk. Furthermore, we will introduce a novel result on spectral stability related to triangles.
Doubly Stochastic Matrices and Modified Laplacian Matrices of Graphs
Enide Andrade
University of Aveiro (Portugal)
Plenary Talk 4: 30 Oct – 8:30am
We consider modified Laplacian matrices of graphs, where the modification consists of adding the identity matrix to the Laplacian matrix of a graph . This results in a positive definite matrix
. The inverse of
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
. 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.
We survey some of these results and outline some ongoing research on this topic.
Eigenvalue location technique and the largest eigenvalue of graphs
Francesco Belardo
University of Naples (Italy)
Plenary Talk 5: 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 . 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.
Spectral extrema of graphs with a given size and a forbidden subgraph
Xueliang Li
Nankai University (China)
Plenary Talk 6: 31 Oct – 2:30pm
The spectral radius of a graph is the largest eigenvalue of the adjacency matrix of the graph. A graph is said to forbid a given subgraph if the graph does not contain the given subgraph as a subgraph. In this talk we will present some results on the spectral extrema of graphs with a given size and a forbidden subgraph, such as a clique, a cycle, a theta graph, a book graph, a friendship graph, a fan graph, and a wheel graph, etc.
This is a joint work with my PhD student Ms. Jing Gao. We shall honor the contributions of Prof. Vilmar Trevisan on the occasion of his 65th birthday.