Counting orientations of graphs with no strongly connected tournaments

Abstract

Let Sk(n) be the maximum number of orientations of an n-vertex graph G in which no copy of Kk is strongly connected. For all integers n, k ≥ 4 where n ≥ 5 or k ≥ 5, we prove that Sk(n) = 2tk - 1(n), where tk-1(n) is the number of edges of the n-vertex (k - 1)-partite Turán graph Tk-1(n). Moreover, we prove that Tk-1(n) is the only graph having 2tk-1(n) orientations with no strongly connected copies of Kk.