OpenAlex ·
A proof of the Murty--Simon conjecture on diameter-$2$-critical graphs
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.39032
- Original
- Read it at the publisher
- Topics
Abstract
The Murty-Simon conjecture states that every $n$-vertex diameter-$2$-critical graph has at most $\lfloor n^2/4 \rfloor$ edges, with equality only for the balanced complete bipartite graph. Using regularity methods, Füredi proved this for all sufficiently large $n$ (specifically, $n$ greater than a tower of $2$'s of height roughly $10^{14}$). We present a proof of the Murty-Simon conjecture that works for all $n$. A proof of the $\lfloor n^2/4 \rfloor$ bound was originally found by AI; we simplified this proof and extended its ideas to get a proof of the full conjecture.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Using Transformers to Generate 3-Manifold Triangulations
Mutation-acyclicity in rank four is decidable but not semialgebraic
Contributions to the Stable Derived Categories of Gorenstein Rings
Deterministic Root-Finding over Finite Fields with Elliptic Curves
Bistability with equal and independent removal in small bimolecular networks
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.