2
$\begingroup$

I wish to know the latest bound on the number of edges a graph of girth greater than or equal to $t$ can have.

Specifically, I heard somewhere that a graph of girth greater than or equal to $t$ can have $O(n^{2-\frac{2}{t}})$ edges. Is it true?

$\endgroup$
2
  • $\begingroup$ Why the downvote? $\endgroup$
    – vidyarthi
    Commented Jul 11, 2023 at 8:36
  • 2
    $\begingroup$ There’s something weird about your guess here: increasing $t$ should force the graph to have fewer edges, but the bound you wrote goes in the other way. $\endgroup$ Commented Jan 2 at 5:27

2 Answers 2

3
$\begingroup$

A graph of girth $g$ can have at most $O(n^{1+\frac1{\lfloor\frac{g-1}2\rfloor}})$ edges. This is known as the Moore bound, though now the only reference I could find online right now is this one: Dutton and Brigham - Edges in graphs with large girth.

$\endgroup$
3
$\begingroup$

Start with a graph $G$ with average degree $d$. By deleting low-degree vertices, you can pass to a subgraph $G'$ with minimum degree $d/2$. Fixing some vertex $v_0$ in $G'$, we should have that there are $\ge (d/2-1)^i$ vertices at distance $i$ from $v_0$, for every $i\le \lfloor (g-1)/2\rfloor$ (this is proven by induction since otherwise you would create a cycle of length $\le g$, if there was some vertex at distance $i<\lfloor (g-1)/2\rfloor$ which had $\ge 2$ neighbors at distance $\le i$ to $v_0$).

Thus, we see that $|V(G')|\ge (d/2-1)^{\lfloor (g-1)/2\rfloor}$. This recovers the bound domotorp mentioned.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .