I am unable to get the bound on the maximum size of a graph of order $n$ with girth $g$. Is there any literature regarding this. I know that there is an asymptotic bound on the size of a graph $G$ with even girth $2k$ and order $n$. Is there a similar one for arbitrary grith? Thanks beforehand.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Could you please tell what is bound for even girth? It should be easily extended for odd girth. $\endgroup$– Inuyasha YagamiCommented Jul 5, 2023 at 13:49
-
$\begingroup$ @InuyashaYagami From here, theorem 4.1 and its corollary, we have that the maximum number of edges for a graph with order $n$ and even girth $2k$ is less than $\frac{n+n^{1+\frac1{k}}}{2}$. Note, however that when we take the complete graph, which has girth $3$, this bound fails $\endgroup$– vidyarthiCommented Jul 5, 2023 at 15:40
Add a comment
|