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

作者：Savchenko S V^*

来源：Journal of Graph Theory, 2012, 70(4): 361-383.

DOI：10.1002/jgt.20615

• circuit
• non-critical vertex
• tournament
• transitive tournament
• MSC 2010
• 05C20
• 05C38

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 2h=n-d+1, the minimum number of circuits of length n-h in a tournament of this class is equal to n-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 Td,n 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 l in T is not less than that in Td,n for each possible l. Moreover, if these two numbers are equal to each other for some given l=n-d+3,...,d, where d=(n+3)/2, then T is isomorphic to either Td,n or its converse Td,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.

• 出版日期2012-8