052: Extremal Graphs with Small Girth

Proposed by Michael Codish, Alice Miller, Patrick Prosser, Peter Stuckey

Given a simple undirected graph $G = (V,E)$, where $V$ is the set of vertices and $E$ the set of undirected edges, the edge {$u,v$} is in $E$ if and only if vertex $u$ is adjacent to vertex $v$ in $G$. The graph is simple in that there are no loop edges, i.e. we have no edges of the form {$v,v$}.

The order ($m$) of a graph is the number of vertices in that graph and the size ($n$) is the number of edges. The girth ($k$) is the length of the smallest cycle contained in the graph.

Let $fk(m)$ denote the maximum number of edges in a graph with m vertices and girth greater than $k$ (i.e. with no cycles of length $k$ or less). The number of non-isomorphic extremal graphs with m vertices and $fk(m)$ edges is denoted $Fk(m)$.

The problem is then, for given values of $m$ and $k$, find $fk(m)$ and additionally to find $Fk(m)$. That is, what is the maximal number of edges in a graph with m vertices and girth greater than $k$ and how many such unique graphs are there?