Tournaments whose Indecomposability Graph Admits a Vertex Cover of Size \(2\)

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 – 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 tournament whose intervals are trivial is indecomposable; otherwise, it is decomposable. With each indecomposable tournament \(T\), we associate its indecomposability graph \(\mathbb{I}(T)\) defined as follows: the vertices of \(\mathbb{I}(T)\) are those of \(T\) and its edges are the unordered pairs of distinct vertices \(\{x, y\}\) such that \(T -\{x, y\}\) is indecomposable. We characterize the indecomposable tournaments \(T\) whose \(\mathbb{I}(T)\) admits a vertex cover of size \(2\).