Critical and Maximal Directed Graphs

In this Memoir we investigate finite directed graphs (digraphs) without loops with extreme properties with respect to certain metric or quasi-metric functionals. An n-vertex digraph G is called critical with respect to some functional F if adding an arbitrary missing arc to G results in decreasing F, and maximal if G has the maximum number of arcs among all n-vertex digraphs with the same value of F. The distance from a vertex x to a vertex y in the digraph G equals the minimum number of arcs in a directed path from x to y; if there are no directed path from x to y, then the distance is infinite. The quasi-distance between x and y is defined as the minimum of distances from x to y and from y to x. We also define in the usual way diameter, radius and, similarly, quasi-diameter and quasi-radius of the digraph G. We characterize up to isomorphism the critical digraphs with infinite value of diameter, radius, quasi-diameter and quasi-radius. Moreover, the maximal digraphs with finite value of radius and quasi-diameter are studied. And we leave the problem of describing the maximal digraphs with finite quasi-radius to the next generation.