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\).
Reviewer: J. W. Moon (Edmonton)
MSC:
05C20 | Directed graphs (digraphs), tournaments |
05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |