The Number of Out-Pancyclic Vertices in a Strong Tournament

An arc in a tournament T with n ≥ 3 vertices is called pancyclic, if it belongs to a cycle of length l for all 3 ≤ l ≤ n. We call a vertex u of T an out-pancyclic vertex of T, if each out-arc of u is pancyclic in T. Yao et al. (Discrete Appl. Math. 99, 245–249, 2000) proved that every strong tournament contains an out-pancyclic vertex. For strong tournaments with minimum out-degree 1, Yao et al. found an infinite class of strong tournaments, each of which contains exactly one out-pancyclic vertex. In this paper, we prove that every strong tournament with minimum out-degree at least 2 contains three out-pancyclic vertices. Our result is best possible since there is an infinite family of strong tournaments with minimum degree at least 2 and no more than 3 out-pancyclic vertices.     

The structure of 4‐strong tournaments containing exactly three out‐arc pancyclic vertices

Yao et al. (Discrete Appl Math 99 (2000), 245–249) proved that every strong tournament contains a vertex u such that every out‐arc of u is pancyclic and conjectured that every k‐strong tournament contains k such vertices. At present, it is known that this conjecture is true for k = 1, 2, 3 and not true for k?4. In this article, we obtain a sufficient and necessary condition for a 4‐strong tournament to contain exactly three out‐arc pancyclic vertices, which shows that a 4‐strong tournament contains at least four out‐arc pancyclic vertices except for a given class of tournaments. Furthermore, our proof yields a polynomial algorithm to decide if a 4‐strong tournament has exactly three out‐arc pancyclic vertices.     

Vertex‐pancyclicity of hypertournaments

A hypertournament or a k‐tournament, on n vertices, 2≤k≤n, is a pair T=(V, E), where the vertex set V is a set of size n and the edge set E is the collection of all possible subsets of size k of V, called the edges, each taken in one of its k! possible permutations. A k‐tournament is pancyclic if there exists (directed) cycles of all possible lengths; it is vertex‐pancyclic if moreover the cycles can be found through any vertex. A k‐tournament is strong if there is a path from u to v for each pair of distinct vertices u and v. A question posed by Gutin and Yeo about the characterization of pancyclic and vertex‐pancyclic hypertournaments is examined in this article. We extend Moon's Theorem for tournaments to hypertournaments. We prove that if k≥8 and n≥k + 3, then a k‐tournament on n vertices is vertex‐pancyclic if and only if it is strong. Similar results hold for other values of k. We also show that when n≥7, k≥4, and n≥k + 2, a strong k‐tournament on n vertices is pancyclic if and only if it is strong. The bound n≥k+ 2 is tight. We also find bounds for the generalized problem when we extend vertex‐pancyclicity to require d edge‐disjoint cycles of each possible length and extend strong connectivity to require d edge‐disjoint paths between each pair of vertices. Our results include and extend those of Petrovic and Thomassen. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 338–348, 2010     

Solution of a conjecture of Tewes and Volkmann regarding extendable cycles in in‐tournaments

A directed cycle C of a digraph D is extendable if there exists a directed cycle C′ in D that contains all vertices of C and an additional one. In 1989, Hendry defined a digraph D to be cycle extendable if it contains a directed cycle and every non‐Hamiltonian directed cycle of D is extendable. Furthermore, D is fully cycle extendable if it is cycle extendable and every vertex of D belongs to a directed cycle of length three. In 2001, Tewes and Volkmann extended these definitions in considering only directed cycles whose length exceed a certain bound 3≤k<n: a digraph D is k ‐extendable if every directed cycle of length t, where k≤t<n, is extendable. Moreover, D is called fully k ‐extendable if D is k ‐extendable and every vertex of D belongs to a directed cycle of length k. An in‐tournament is an oriented graph such that the in‐neighborhood of every vertex induces a tournament. This class of digraphs which generalizes the class of tournaments was introduced by Bang‐Jensen, Huang and Prisner in 1993. Tewes and Volkmann showed that every connected in‐tournament D of order n with minimum degree δ≥1 is ( ) ‐extendable. Furthermore, if D is a strongly connected in‐tournament of order n with minimum degree δ=2 or , then D is fully ( ) ‐extendable. In this article we shall see that if , every vertex of D belongs to a directed cycle of length , which means that D is fully ( ) ‐extendable. This confirms a conjecture of Tewes and Volkmann. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 82–92, 2010     

Pancyclic arcs and connectivity in tournaments

A tournament is an orientation of the edges of a complete graph. An arc is pancyclic in a tournament T if it is contained in a cycle of length l, for every 3 ≤ l ≤ |T|. Let p(T) denote the number of pancyclic arcs in a tournament T. In 4 , Moon showed that for every non‐trivial strong tournament T, p(T) ≥ 3. Actually, he proved a somewhat stronger result: for any non‐trivial strong tournament h(T) ≥ 3 where h(T) is the maximum number of pancyclic arcs contained in the same hamiltonian cycle of T. Moreover, Moon characterized the tournaments with h(T) = 3. All these tournaments are not 2‐strong. In this paper, we investigate relationship between the functions p(T) and h(T) and the connectivity of the tournament T. Let p_k(n) := min {p(T), T k‐strong tournament of order n} and h_k(n) := min{h(T), T k‐strong tournament of order n}. We conjecture that (for k ≥ 2) there exists a constant α_k> 0 such that p_k(n) ≥ α_kn and h_k(n) ≥ 2k+1. In this paper, we establish the later conjecture when k = 2. We then characterized the tournaments with h(T) = 4 and those with p(T) = 4. We also prove that for k ≥ 2, p_k(n) ≥ 2k+3. At last, we characterize the tournaments having exactly five pancyclic arcs. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 87–110, 2004     

Each 3-strong Tournament Contains 3 Vertices Whose Out-arcs Are Pancyclic

An arc in a tournament T with n ≥ 3 vertices is called pancyclic, if it is in a cycle of length k for all 3 ≤ k ≤ n. Yeo (Journal of Graph Theory, 50 (2005), 212–219) proved that every 3-strong tournament contains two distinct vertices whose all out-arcs are pancyclic, and conjectured that each 2-strong tournament contains 3 such vertices. In this paper, we confirm Yeo’s conjecture for 3-strong tournaments. The author is an associate member of “Graduiertenkolleg: Hierarchie und Symmetrie in mathematischen Modellen (DFG)” at RWTH Aachen University, Germany.     

Edge‐disjoint Hamiltonian cycles in hypertournaments

We introduce a method for reducing k‐tournament problems, for k ≥ 3, to ordinary tournaments, that is, 2‐tournaments. It is applied to show that a k‐tournament on n ≥ k + 1 + 24d vertices (when k ≥ 4) or on n ≥ 30d + 2 vertices (when k = 3) has d edge‐disjoint Hamiltonian cycles if and only if it is d‐edge‐connected. Ironically, this is proved by ordinary tournament arguments although it only holds for k ≥ 3. We also characterizatize the pancyclic k‐tournaments, a problem posed by Gutin and Yeo.(Our characterization is slightly incomplete in that we prove it only for n large compared to k.). © 2005 Wiley Periodicals, Inc. J Graph Theory     

Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments

Given a k‐arc‐strong tournament T, we estimate the minimum number of arcs possible in a k‐arc‐strong spanning subdigraph of T. We give a construction which shows that for each k ≥ 2, there are tournaments T on n vertices such that every k‐arc‐strong spanning subdigraph of T contains at least arcs. In fact, the tournaments in our construction have the property that every spanning subdigraph with minimum in‐ and out‐degree at least k has arcs. This is best possible since it can be shown that every k‐arc‐strong tournament contains a spanning subdigraph with minimum in‐ and out‐degree at least k and no more than arcs. As our main result we prove that every k‐arc‐strong tournament contains a spanning k‐arc‐strong subdigraph with no more than arcs. We conjecture that for every k‐arc‐strong tournament T, the minimum number of arcs in a k‐arc‐strong spanning subdigraph of T is equal to the minimum number of arcs in a spanning subdigraph of T with the property that every vertex has in‐ and out‐degree at least k. We also discuss the implications of our results on related problems and conjectures. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 265–284, 2004     

The number of pancyclic arcs in a k‐strong tournament

A tournament is a digraph, where there is precisely one arc between every pair of distinct vertices. An arc is pancyclic in a digraph D, if it belongs to a cycle of length l, for all 3 ≤ l ≤ |V (D) |. Let p(D) denote the number of pancyclic arcs in a digraph D and let h(D) denote the maximum number of pancyclic arcs belonging to the same Hamilton cycle of D. Note that p(D) ≥ h(D). Moon showed that h(T) ≥ 3 for all strong non‐trivial tournaments, T, and Havet showed that h(T) ≥ 5 for all 2‐strong tournaments T. We will show that if T is a k‐strong tournament, with k ≥ 2, then p(T) ≥ 1/2, nk and h(T) ≥ (k + 5)/2. This solves a conjecture by Havet, stating that there exists a constant α_k, such that p(T) ≥ α_k n, for all k‐strong tournaments, T, with k ≥ 2. Furthermore, the second results gives support for the conjecture h(T) ≥ 2k + 1, which was also stated by Havet. The previously best‐known bounds when k ≥ 2 were p(T) ≥ 2k + 3 and h(T) ≥ 5. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Quasi-transitive digraphs

A digraph is quasi-transitive if there is a complete adjacency between the inset and the outset of each vertex. Quasi-transitive digraphs are interseting because of their relation to comparability graphs. Specifically, a graph can be oriented as a quasi-transitive digraph if and only if it is a comparability graph. Quasi-transitive digraphs are also of interest as they share many nice properties of tournaments. Indeed, we show that every strongly connected quasi-transitive digraphs D on at least four vertices has two vertices v₁ and v₂ such that D – v_i is strongly connected for i = 1, 2. A result of tournaments on the existence of a pair of arc-disjoint in- and out-branchings rooted at the same vertex can also be extended to quasi-transitive digraphs. However, some properties of tournaments, like hamiltonicity, cannot be extended directly to quasi-transitive digraphs. Therefore we characterize those quasi-transitive digraphs which have a hamiltonian cycle, respectively a hamiltonian path. We show the existence of highly connected quasi-transitive digraphs D with a factor (a collection of disjoint cycles covering the vertex set of D), which have a cycle of every length 3 ≦ k ≦ |V(D)| ? 1 through every vertex and yet they are not hamiltonian. Finally we characterize pancyclic and vertex pancyclic quasi-transitive digraphs. © 1995, John Wiley & Sons, Inc.     

Kings in semicomplete multipartite digraphs

A digraph obtained by replacing each edge of a complete p‐partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete p‐partite digraph, or just a semicomplete multipartite digraph. A semicomplete multipartite digraph with no cycle of length two is a multipartite tournament. In a digraph D, an r‐king is a vertex q such that every vertex in D can be reached from q by a path of length at most r. Strengthening a theorem by K. M. Koh and B. P. Tan (Discr Math 147 (1995), 171–183) on the number of 4‐kings in multipartite tournaments, we characterize semicomplete multipartite digraphs, which have exactly k 4‐kings for every k = 1, 2, 3, 4, 5. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 177‐183, 2000     

Regular representations of finite groups as automorphism groups of k‐tournaments

It was shown by Babai and Imrich [2] that every finite group of odd order except and admits a regular representation as the automorphism group of a tournament. Here, we show that for k ≥ 3, every finite group whose order is relatively prime to and strictly larger than k admits a regular representation as the automorphism group of a k‐tournament. Our constructions are elementary, suggesting that the problem is significantly simpler for k‐tournaments than for binary tournaments. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 238–248, 2002     

Cycle factors in strongly connected local tournaments

A digraph without loops, multiple arcs and directed cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. A digraph is 2-connected if the removal of an arbitrary vertex results in a strongly connected digraph.In 2004 and 2005, Li and Shu investigated the structure of strongly connected, but not 2-connected tournaments. Using their structural results they were able to give sufficient conditions for a strongly connected tournament T to have complementary cycles or a k-cycle factor, i.e. a set of k vertex disjoint cycles that span the vertex set of T.Inspired by the articles of Li and Shu we develop in this paper the structure necessary for a strongly connected local tournament to be not cycle complementary. Using this structure, we are able to generalize and transfer various results of Li and Shu to the class of local tournaments.     

Feedback Vertex Sets in Tournaments

We study combinatorial and algorithmic questions around minimal feedback vertex sets (FVS) in tournament graphs. On the combinatorial side, we derive upper and lower bounds on the maximum number of minimal FVSs in an n‐vertex tournament. We prove that every tournament on n vertices has at most 1.6740ⁿ minimal FVSs, and that there is an infinite family of tournaments, all having at least 1.5448ⁿ minimal FVSs. This improves and extends the bounds of Moon (1971). On the algorithmic side, we design the first polynomial space algorithm that enumerates the minimal FVSs of a tournament with polynomial delay. The combination of our results yields the fastest known algorithm for finding a minimum‐sized FVS in a tournament.     

Solution of a covering problem related to labelled tournaments

Suppose we have a tournament with edges labelled so that the edges incident with any vertex have at most k distinct labels (and no vertex has outdegree 0). Let m be the minimal size of a subset of labels such that for any vertex there exists an outgoing edge labelled by one of the labels in the subset. It was known that m ≤ (^k+1₂) for any tournament. We show that this bound is almost best possible, by a probabilistic construction of tournaments with m = O(k²/log k). We give explicit tournaments with m = k^2−o(1). If the number of vertices is bounded by N < 2^k₁ we have a better upper bound of m = O(k log N), which is again almost optimal. We also consider a relaxation of this problem in which instead of the size of a subset of labels we minimize the total weight of a fractional set with analogous properties. In that case the optimal bound is 2k − 1. © 1996 John Wiley & Sons, Inc.     

On n-partite Tournaments with Unique n-cycle

An n-partite tournament is an orientation of a complete n-partite graph. An n-partite tournament is a tournament, if it contains exactly one vertex in each partite set. Douglas, Proc. London Math. Soc. 21 (1970) 716–730, obtained a characterization of strongly connected tournaments with exactly one Hamilton cycle (i.e., n-cycle). For n≥3, we characterize strongly connected n-partite tournaments that are not tournaments with exactly one n-cycle. For n≥5, we enumerate such non-isomorphic n-partite tournaments.     

Regular Hypertournaments and Arc‐Pancyclicity

A k‐hypertournament H on n vertices () is a pair , where V is the vertex set of H and A is a set of k‐tuples of vertices, called arcs, such that for all subsets with , A contains exactly one permutation of S as an arc. Recently, Li et al. showed that any strong k‐hypertournament H on n vertices, where , is vertex‐pancyclic, an extension of Moon's theorem for tournaments. In this article, we examine several generalizations of regular tournaments and prove the following generalization of Alspach's theorem concerning arc‐pancyclicity: Every Σ‐regular k‐hypertournament on n vertices, where , is arc‐pancyclic.     

Disjoint 3‐Cycles in Tournaments: A Proof of The Bermond–Thomassen Conjecture for Tournaments

We prove that every tournament with minimum out‐degree at least contains k disjoint 3‐cycles. This provides additional support for the conjecture by Bermond and Thomassen that every digraph D of minimum out‐degree contains k vertex disjoint cycles. We also prove that for every , when k is large enough, every tournament with minimum out‐degree at least contains k disjoint cycles. The linear factor 1.5 is best possible as shown by the regular tournaments.     

On the Strong <Emphasis Type="Italic">n</Emphasis>-partite Tournaments with Exactly Two Cycles of Length <Emphasis Type="Italic">n</Emphasis> − 1

Gutin and Rafiey (Australas J. Combin. 34 (2006), 17-21) provided an example of an n-partite tournament with exactly n ? m + 1 cycles of length of m for any given m with 4 ≤ m ≤ n, and posed the following question. Let 3 ≤ m ≤ n and n ≥ 4. Are there strong n-partite tournaments, which are not themselves tournaments, with exactly n ? m + 1 cycles of length m for two values of m? In the same paper, they showed that this question has a negative answer for two values n ? 1 and n. In this paper, we prove that a strong n-partite tournament with exactly two cycles of length n ? 1 must contain some given multipartite tournament as subdigraph. As a corollary, we also show that the above question has a negative answer for two values n ? 1 and any l with 3 ≤ l ≤ n and l ≠ n ? 1.     

Out-arc pancyclicity of vertices in tournaments

Yao, Guo and Zhang [T. Yao, Y. Guo, K. Zhang, Pancyclic out-arcs of a vertex in a tournament, Discrete Appl. Math. 99 (2000) 245-249.] proved that every strong tournament contains a vertex u such that every out-arc of u is pancyclic. In this paper, we prove that every strong tournament with minimum out-degree at least two contains two such vertices. Yeo [A. Yeo, The number of pancyclic arcs in a k-strong tournament, J. Graph Theory 50 (2005) 212-219.] conjectured that every 2-strong tournament has three distinct vertices {x,y,z}, such that every arc out of x,y and z is pancyclic. In this paper, we also prove that Yeo’s conjecture is true.