PreprintarXiv licencearXiv
Maximizing Algebraic Connectivity with 2(n−2) Edges: The Large Vertex Number Case
Abstract
Kolokolnikov conjectured that, among all simple graphs on n vertices with exactly 2(n−2) edges, the complete bipartite graph maximizes algebraic connectivity. This paper proves the conjecture. The underlying Lean~4 formalization was generated with MerLean and checked by the Lean kernel.
Related
- Toward Maximizing Algebraic Connectivity via Density-Dependent Backbone Construction and Reinforcement Learning Completion
- A Unified Linear Programming Approach for Maximizing Vertex-Degree-Based Indices of Trees
- Maximizing the number of cliques in Kr+1-free graphs with forbidden properties
- On the number of edges in quasiplanar graphs
- Trace-minimal graphs maximizing the number of spanning trees
BibTeX
@misc{zhu2026maximizing,
title = {{Maximizing Algebraic Connectivity with $2(n-2)$ Edges: The Large Vertex Number Case}},
author = {Zeru Zhu and Jinzheng Li and Yuanjie Ren and Ji Liu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.07360},
eprint = {2608.07360},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.07360},
}
RIS
TY - UNPB
TI - Maximizing Algebraic Connectivity with 2(n−2) Edges: The Large Vertex Number Case
AU - Zeru Zhu
AU - Jinzheng Li
AU - Yuanjie Ren
AU - Ji Liu
PY - 2026
DA - 2026/09/13
PB - arXiv
DO - 10.48550/arxiv.2608.07360
UR - https://arxiv.org/abs/2608.07360
AB - Kolokolnikov conjectured that, among all simple graphs on n vertices with exactly 2(n−2) edges, the complete bipartite graph maximizes algebraic connectivity. This paper proves the conjecture. The underlying Lean~4 formalization was generated with MerLean and checked by the Lean kernel.
ER -