Maximizing the algebraic connectivity of graphs of given order and size: a proof of a conjecture of Kolokolnikov

Abstract

The algebraic connectivity of a graph $G$ is a well-studied graph invariant that is related to other properties of the graph such as connectivity and expansion. Given $n$ and $m$, $α(n,m)$ is the maximum algebraic connectivity of a graph with $n$ vertices and $m$ edges. In 2015, Kolokolnikov conjectured that $α(n,2n-4)=2$ for $n\geq 4$, and verified this claim computationally for $n \le 12$. In this paper, we prove Kolokolnikov's conjecture. We also show that $α(n,3(n-3)) = 3$ is false in general. %Combined with the computational verification for $n \le 12$, this yields $α(n,2n-4)=2$ for all admissible values of $n$.

Disclosure

“annan acknowledges financial support from ANRF-CRG, India (File No. CRG/2023/002747). Rahul Roy thanks the University Grants Commission (UGC), India, for financial support (NTA Ref. No. 231610209574). The authors acknowledge the use of ChatGPT for improving the exposition of the manuscript, refining some of the proofs and constructing the example. All mathematical statements have been independently verified by the authors, who are solely responsible for the correctness of the re”

PDF page 23

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:08:14.206256Z

Structural counts