An improved Moore bound for girths seven and eleven
Source: arxiv.org/abs/2611.26037
Let $n(d,k)$ be the minimum number of vertices of a graph of minimum degree $d$ and girth at least $g=2k+1$. A simple counting argument gives the classical lower bound $n(d,k)\ge m(d,k)=1+d\sum_{i=0}^{k-1}(d-1)^i$, known as the Moore bound and dating back at least to 1960. Apart from complete graphs and odd cycles, graphs attaining this lower bound can exist only for girth $5$ and degrees $3,7$ and $57$ (Hoffman and Singleton 1960; Bannai and Ito 1973; Damerell 1973). Nevertheless, for more than sixty years this lower bound has not been substantially improved beyond an additive constant. For…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.26037
curl -X POST /api/v1/records/arxiv/2611.26037/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.26037/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'