\(\text{TT}_n\)-maximal digraphs of the minimum size (Q1970725)

\(\text{TT}_n\) denotes the transitive tournament on \(n\) vertices. A digraph \(D\) is \(\text{TT}_n\)-maximal if it contains no \(\text{TT}_n\), but loses that property under the addition of any arc. The reviewer and Harary [\textit{W. G. Brown} and \textit{Frank Harary}, Extremal digraphs. Comb. Theory Appl. Colloquia Math. Soc. János Bolyai 4, 135-198 (1970; Zbl 0209.28501)] determined the maximum number of arcs in a \(\text{TT}_n\)-maximal digraph, and the structure of the extremal digraphs. In the present paper the author is concerned with the minimum number of arcs in a \(\text{TT}_n\)-maximal digraph on \(m\) vertices \((m\geq n)\). In Theorem 4 it is shown that the minimum size of \(\text{TT}_3\)-maximal digraphs on \(m\geq 3\) vertices is \(2m-3\), and the structure of these digraphs is determined. In Theorem 7 it is shown that the minimum size of \(\text{TT}_n\)-maximal digraphs on \(n+1\) vertices is \(n^2-4\), and their structure also is determined. The author conjectures that, in general, the minimum size of a \(\text{TT}_n\)-maximal digraph of order \(m\) \((3\leq n\leq m)\) is \((2m-n)(n-2)\), and also offers a conjecture as to the structure of these digraphs.