Non‐Critical Vertices and Long Circuits in Strong Tournaments of Order n and Diameter d

Let T be a strong tournament of order n ≥ 4 with diameter d ≥ 2 . A vertex w in T is non‐critical if the subtournament T − w is also strong. In the opposite case, it is a critical vertex. In the present article, we show that T has at most max { 2 , d − 1 } critical vertices. This fact and Moon's vertex‐pancyclic theorem imply that for d ≥ 3 , it contains at least n − d + 1 circuits of length n − 1 . We describe the class of all strong tournaments of order n ≥ 4 with diameter d ≥ 3 for which this lower bound is achieved and show that for 2 h ≤ n − d + 1 , the minimum number of circuits of length n − h in a tournament of this class is equal ton − d + 1h. In turn, the minimum among all strong tournaments of order n ≥ 3 with diameter 2 grows exponentially with respect to n for any given h ≥ 0 . Finally, for n > d ≥ 3 , we select a strong tournament T d , nof order n with diameter d and conjecture that for any strong tournament T of order n whose diameter does not exceed d , the number of circuits of length ℓ in T is not less than that in T d , nfor each possible ℓ. Moreover, if these two numbers are equal to each other for some given ℓ = n − d + 3 , ... , d , where d ≥ ( n + 3 ) / 2 , then T is isomorphic to either T d , nor its converse T d , n − . For d = n − 1 , this conjecture was proved by Las Vergnas. In the present article, we confirm it for the case d = n − 2 . In an Appendix, some problems concerning non‐critical vertices are considered for generalizations of tournaments.