| For any directed graph with finite diameter d, it is always the case that g ≤ d + 1, where the girth g is the length of the shortest cycle in . This thesis examines girth extremal digraphs, that is, directed graphs for which g = d + 1.; The thesis gives both necessary conditions for girth extremality (i.e. properties of girth extremal digraphs), and sufficient conditions for girth extremality (i.e. classes of girth extremal digraphs). Properties include the following. It is shown that in a girth extremal digraph of girth g, every edge is contained in an induced g-cycle. Also, for an edge in a girth extremal digraph, x has out-degree one if and only if y has in-degree one. An emphasis is made, throughout the thesis, on finding bounds on the minimum and maximum number of edges in girth extremal digraphs of particular order and girth. In so doing, an improvement is obtained on a result of Dawes and Meijer [15, pg. 8] that gives a lower bound on the minimum number of edges in a digraph of order n = 6 or n ≥ 8 and diameter two.; There are several classes of girth extremal digraphs found. The lexicographic product of digraphs is used to construct a class of girth extremal digraphs that gives a good lower bound on the maximum number of edges in a girth extremal digraph of order n and girth g, for an infinite number of pairs n, g. As well, a generalization of a class of girth extremal digraphs found by Neufeld [18, pg. 80] is obtained.; Some characterizations are obtained for the girth extremal digraphs within certain classes of digraphs. In particular, characterizations are given of the girth extremal tournaments, as well as the girth extremal bipartite tournaments. Further, characterizations are given of certain sub-classes of the Cayley digraphs. |
