Permalink
Fetching contributors…
Cannot retrieve contributors at this time
18 lines (13 sloc) 1.13 KB
Title Proposer Category
Extremal Graphs with Small Girth
Michael Codish
Alice Miller
Patrick Prosser
Peter Stuckey
Combinatorial mathematics

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?