• Homepage
  +
• Research results
  +
• Projects
  +
• Seminars and Colloquiums
  +
• Conferences
  +
• International Collaborations
  +

Project name: Lazy walk counts and spectral radius of threshold graphs, LZWK (2023-2026)

Project Reference No: 6767, supported by the Science Fund of the Republic of Serbia

Project leader: Sanja Stevanović

Project description

The focus of this project is the improvement in the methodology of comparing, for two given threshold graphs, the numbers of walks within each graph, and its use toward the resolution of a few difficult problems in spectral graph theory. Such methodology was so far used only for trees and this will be the first time it is applied to graphs with large edge density.
The first problem is to characterize graphs with the maximum spectral radius among connected graphs with given numbers of vertices and edges, which is open for more than 35 years. It is well known that the candidates for extremal graphs are threshold graphs, but only a few partial results have been obtained so far. We aim to attack this problem from a novel perspective of enumerating lazy walks and comparing their numbers between different threshold graphs.
The second goal is to study two conjectures on the sum of spectral radii of a graph and its complement, for which candidate extremal graphs are also threshold graphs. We will first aim to establish a graph theoretical proof of the Nikiforov conjecture, for which the only known proof so far uses analytical constructs known as graphons. We will further aim to provide tight estimates of the spectral radii of threshold graphs in order to approach the more precise Aouchiche-Hansen conjecture.
As a risk-free side project, we will work on a proper implementation of reinforcement learning, a well-known artificial intelligence methodology, for constructing (counter)examples in graph theory, motivated by the recent pioneering application by Adam Zsolt Wagner and our own experiences with it.
The outcome of this project will add novel theoretical methods to spectral graph theory, so its main beneficiaries are other researchers in this field. At the national level, this project will strengthen the international reputation of the Serbian school of graph theory.

List of researchers

Sanja Stevanović		Research associate professor		Mathematical Institute SANU		sanja.stevanovic@mi.sanu.ac.rs
Ivan Damnjanović		Doctoral student		Faculty of Electronic Engineering, University of Niš		ivan.damnjanovic@elfak.ni.ac.rs
Tatjana Davidović		Research full professor		Mathematical Institute SANU		tanjad@mi.sanu.ac.rs
Dragan Stevanović		Research full professor		external collaborator		dragan_stevanovic@mi.sanu.ac.rs