The \((-1)\)-Critically Duo-Free Tournaments

Abstract

Given a tournament \(T = (V, A)\), a subset \(X\) of \(V\) is an interval of \(T\) provided that for any \(a, b \in X\) and \(x \in V \setminus X\), \((a, x) \in A\) if and only if \((b, x) \in A\). For example, \(\emptyset\), \(\{x\}\) (\(x \in V\)), and \(V\) are intervals of \(T\), called trivial intervals. A two-element interval of \(T\) is called a duo of \(T\). Tournaments that do not admit any duo are called duo-free tournaments. A vertex \(x\) of a duo-free tournament is \(d\)-critical if \(T – x\) has at least one duo. In 2005, J.F. Culus and B. Jouve [5] characterized the duo-free tournaments, all of whose vertices are d-critical, called tournaments without acyclic interval. In this paper, we characterize the duo-free tournaments that admit exactly one non-d-critical vertex, called (-1)-critically duo-free tournaments.