Non-Critical Vertices and Long Circuits in Strong Tournaments of Order n and Diameter d
Let T be a strong tournament of order with diameter . A vertex w in T is non-critical if the subtournament is also strong. In the opposite case, it is a critical vertex. In the present article, we show that T has at most critical vertices. This fact and Moon's vertex-pancyclic theorem imply that for , it contains at least circuits of length . We describe the class of all strong tournaments of order with diameter for which this lower bound is achieved and show that for , the minimum number of circuits of length in a tournament of this class is equal to . In turn, the minimum among all strong tournaments of order with diameter 2 grows exponentially with respect to n for any given . Finally, for , we select a strong tournament of 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 for each possible ?. Moreover, if these two numbers are equal to each other for some given , where , then T is isomorphic to either or its converse . For , this conjecture was proved by Las Vergnas. In the present article, we confirm it for the case . In an Appendix, some problems concerning non-critical vertices are considered for generalizations of tournaments.
circuit tournament non-critical vertex transitive tournament msc 2010 05c20 05c38