Abstract:

In this paper, we consider the achievability of the maximum and minimum numbers of occurrences of 3-circuits in Eulerian orientations of complete graphs missing a transitive subset of edges: complete graphs with an even number of vertices and a perfect matching removed, and those with an odd number of vertices and a Hamiltonian cycle removed. For each of these families of digraphs, we obtain upper and lower estimates for the number of 3-circuits and prove their achievability. Previously, orientations that are extreme with respect to the number of 4-circuit occurrences have been investigated in [1].