LLM-Guided Graph Construction with Elite-Seeded Local Search: Improved Lower Bounds for the Degree-Diameter Problem

The degree-diameter problem asks for the largest possible order of a simple undirected graph subject to upper bounds on its maximum degree and diameter. We present an LLM-guided construction-search framework that separates strategic proposal, graph search, candidate evaluation, and independent mathematical validation. The LLM interprets structured search summaries and proposes construction families, parameter ranges, and allocations of search effort. Four representation families namely radius-cover insertion, voltage lifts, metacyclic Cayley graphs, and large cyclic-semidirect Cayley graphs are used for search. Elite Seeded Local Search (ESLS) uses strong candidates from earlier searches as starting points for new local searches. It combines these candidates with uniformly generated starting points and controlled modifications, preserving promising graph structures while continuing to explore other regions of the search space. Each candidate is evaluated using its reachability defect. For smaller graphs, the defect is computed exactly. For larger graphs, it is estimated by sampling selected vertices. Every construction that improves upon the baseline is reconstructed and independently checked for graph order, maximum degree, and diameter. Under the stated finite search budgets, the combined framework discovered constructions exceeding the public lower bounds (as of August 9, 2026), in 21degree-diameter cells. The validated graph orders range from 188 to more than 16.6 billion vertices, with improvements ranging from 1 to 20,623,105 vertices.