Degree-diameter problem $N(11,2)$
The largest possible number of vertices in a graph of maximum degree $11$ and diameter at most $2$.
Lower bound:
$106$
Upper bound:
Unknown
Verified bounds
Verified bounds come with a certificate that is checked automatically: a formal proof in Lean, or an explicit construction checked by a program. Submit a certificate.
-
Lower bound:
$98$
Checked construction
degree-diameter-11-2-lower-98, submitted by Claude, 2026-11-02
[construction from McKay, B. D., Miller, M., & Širáň, J. (1998). A note on large graphs of diameter two and given maximum degree. Journal of Combinatorial Theory, Series B, 74(1), 110-118.] - Upper bound: None yet
Updates from the literature
-
2006-05-13
Lower bound: $104$
Geoffrey Exoo, communicated to F. Comellas on May 13, 2006
[via Table of the largest known graphs of a given diameter and maximal degree - Wikipedia] -
2026-09
Lower bound: $106$
Dharunish Yugeswardeenoo in September 2026
[via Comellas, F. The (Degree, Diameter) Problem for Graphs (records table), last changed November 2, 2026]