B. Alspach has proved that a regular tournament is arc-pancyclic. Zhu and Tian proved that if a tournament T = (V, A) with vertex set V, arc set A and order p satisfies that for any arc (vi, u,) of T, if df(uj) + d-(vi) *p -2, then T is arc-pancyclic, where p >7. In this paper we study an extreme problem concerning the k-arc-cyclic property for a class of tournaments.
We say that a tournament T = (V, A) satisfies the condition O@, q) if d+(u) + d-(u) *p -q for any arc (u, u) of T, where q is a positive integer and IV1 =p. Zhu, Tian, Chen and Zhang proved that if a tournament T satisfies the condition O@, q) and p *3q + 3, then T is arc-pancyclic. Let S(p, q) be the set {T = (V, A): T is a tournament with p vertices and T satisfies the condition O(p, q)}; let C*(u, u) be the set {cycles of T with length k using the arc (u, u)}. The aim of this paper is that for a given integer q, we can find an integer m(q, k) such that if p * m(q, k), then for any T E S(p, q), T is k-arc-cyclic; if p G m(q, k) -1, then there exists T E S(p, q) such that T is not k-arc-cyclic. We have found that m(q, 4) = 5q -7, and m(q, 5) = [p*(q)] + 1 or [p*(q)1 + 1, where p*(q) = (1 + 3*)q -(1 + $ .3*).
Some definitions and notations 1. T = (V, A) represents a tournament with vertex set V and arc set A.
- We let p and q be positive integers in this paper. We say T = (V, A) satisfies condition O(p, q) if d+(v) + d-(u) ap -q for any arc (u, V) of T, where IV1 =p, d+(v) is the out-degree of V, and d-(u) is the in-degree of u.
Define
S(p, q) = {T = (V, A): (VI =p, T satisfies condition O(p, q)} S(q) = u S(P, 4).
P 4. For T = (V, A), let Ck(u, V) = {cycles of length k in T using the arc (u, v)}. We say that T = (V, A) is k-arc-cyclic if C,(u, V) 20 for any arc (u, V) of T.
- For integers q, k > 0, define s(q, k) = {T = (V, A): T is k-arc-cyclic, T E S(q)}, m(q, k) = midpl(q, k): if p apl(q, k), then S(p, q) = s(q, k)}. and n(q, k) = max{p,(q, k): if p Sp2(q, k), then there exists T E S(p, q) such that T t$ s(q, k)}.