On the maximal order of cyclicity of antisymmetric directed graphs

AbstractA directed graph G without loops or multiple edges is said to be antisymmetric if for each pair of distinct vertices of G (say u and v), G contains at most one of the two possible directed edges with end-vertices u and v. In this paper we study edge-sets M of an antisymmetric graph G with the following extremal property: By deleting all edges of M from G we obtain an acyclic graph, but by deleting from G all edges of M except one arbitrary edge, we always obtain a graph containing a cycle. It is proved (in Theorem 1) that if M has the above mentioned property, then the replacing of each edge of M in G by an edge with the opposite direction has the same effect as deletion: the graph obtained is acyclic. Further we study the order of cyclicity of G (= the minimal number of edges in such a set M) and the maximal order of cyclicity in an antisymmetric graph with given number n of vertices. It is shown that for n < 10 this number is equal to the maximal number of edge-disjoint circuits in the complete (undirected) graph with n vertices and for n = 10 (and for an infinite set of n's) the first number is greater than the latter