×

Competition indices of tournaments. (English) Zbl 1158.05027

The \(m\)-step competition graph \(C^m(T)\) of a tournament \(T\) has the same vertices as \(T\) and contains the directed edge \(ij\) if and only if there is a vertex \(k\) in \(T\) such that there are directed \(m\)-walks from both \(i\) and \(j\) to \(k\) in \(T\). The competition index \(\text{cindex}(T)\) of \(T\) is the smallest positive integer \(q\) such that \(C^{q+i}(T) = C^{q+r+i}(T)\) for some positive integer \(r\) and all nonnegative integers \(i\). The authors show, among other things, that if \(T\) is a strongly connected \(n\)-tournament, then \(\text{cindex}(T) \leq 4\) and the \(4\) can be replaced by \(3\) when \(n\geq 5\). The first inequality also holds under the weaker assumption that \(T\) has no vertex of out-degree \(0\).

MSC:

05C20 Directed graphs (digraphs), tournaments
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI