Maximizing algebraic connectivity for graphs of given order and size.

Sebastian Cioaba (University of Delaware)

Beyond Graph Laplacians

The algebraic connectivity of a graph is a well-studied graph invariant that is related to other properties of the graph such as connectivity and expansion. Given n and m, define f(n,m) as the maximum algebraic connectivity of a graph with n vertices and m edges. The algebraic connectivity of the complete bipartite graph with partite sets of sizes 2 and n-2 equals 2. In 2015, Kolokolnikov conjectured that f(n,2n-4)=2 for n＞ 3, and verified this claim computationally for n＜12. In this talk, I will describe our recent proof of Kolokolnikov's conjecture. We also show that a potential conjecture that f(n,3(n-3)) = 3 fails in general and f(14,33) ＞ 3. This is joint work with Abhay Jayarajan, M. Rajesh Kannan, Rahul Roy from IIT Hyderabad and is based on the paper https://arxiv.org/abs/2608.09879 I will also give an overview of the work of Nozaki studying the problem of maximizing the algebraic connectivity of regular graphs of given order and size and my work with Gupta, Koolen, Nozaki, Xiang on determining the maximum order of a regular graph of given valency and second eigenvalue.