What question did this study set out to answer?

To establish upper bounds for the number of edges in graphs based on their girth and minimum degree.

March 21, 2026Open Access

Edges In Graphs With Large Girth

Key Points

To establish upper bounds for the number of edges in graphs based on their girth and minimum degree.
Develop mathematical bounds for maximum edges e in relation to order p and girth g.
Analyze cases where minimum degree delta influences edge limits.
Provide asymptotic comparisons for odd girth.
Present numerical comparisons to validate theoretical findings.
An upper bound is established with asymptotic order of p^(1 + 2/(g - 1)) for odd g.
A corollary indicates g ≤ 2 + 2 log(k)(p/4) for k ≥ 2.
Numerical results support the theoretical bounds and offer additional insights into graph behavior.

Abstract

Several upper bounds are given for the maximum number of edges e possible in a graph depending upon its order p, girth g and, in certain cases, minimum degree delta. In particular, one upper bound has an asymptotic order of p1+2/(g-1) when g is odd. A corollary of our final result is that g less-than-or-equal-to 2 + 2 log(k) (p/4) when k = e/p greater-than-or-equal-to 2. Asymptotic and numerical comparisons are also presented.

Edges In Graphs With Large Girth

Key Points

Abstract

Cite This Study