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     

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     

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.     

Path numbers of tournaments

A family of simple (that is, cycle-free) paths is a path decomposition of a tournament T if and only if partitions the acrs of T. The path number of T, denoted pn(T), is the minimum value of | | over all path decompositions of T. In this paper it is shown that if n is even, then there is a tournament on n vertices with path number k if and only if n/2 k n²/4, k an integer. It is also shown that if n is odd and T is a tournament on n vertices, then (n + 1)/2 pn(T) (n² − 1)/4. Moreover, if k is an integer satisfying (i) (n + 1)/2 k n − 1 or (ii) n < k (n² − 1)/4 and k is even, then a tournament on n vertices having path number k is constructed. It is conjectured that there are no tournaments of odd order n with odd path number k for n k < (n² − 1)/4.     

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     

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.     

Vertex pancyclic in‐tournaments

An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. The topic of this paper is to investigate vertex k‐pancyclicity of in‐tournaments of order n, where for some 3 ≤ k ≤ n, every vertex belongs to a cycle of length p for every k ≤ p ≤ n. We give sharp lower bounds for the minimum degree such that a strong in‐tournament is vertex k‐pancyclic for k ≤ 5 and k ≥ n − 3. In the latter case, we even show that the in‐tournaments in consideration are fully (n − 3)‐extendable which means that every vertex belongs to a cycle of length n − 3 and that the vertex set of every cycle of length at least n − 3 is contained in a cycle of length one greater. In accordance with these results, we state the conjecture that every strong in‐tournament of order n with minimum degree greater than is vertex k‐pancyclic for 5 < k < n − 3, and we present a family of examples showing that this bound would be best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 84–104, 2001     

Edge disjoint Hamilton cycles in graphs

Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2(k + 1)‐connected graph G,d _G (u,v) = 2 implies that max{d(u;G), d(v;G)} ≥ (n/2) + 2k, then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000     

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     

Hamiltonian paths and cycles in hypertournaments

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V| = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A$ contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertournament is merely an (ordinary) tournament. A path is a sequence v₁a₁v₂v₃···v_t−1v_t of distinct vertices v₁, v₂,⋖, v_t and distinct arcs a₁, ⋖, a_t−1 such that v_i precedes v_t−1 in a, 1 ≤ i ≤ t − 1. A cycle can be defined analogously. A path or cycle containing all vertices of T (as v_i's) is Hamiltonian. T is strong if T has a path from x to y for every choice of distinct x, y ≡ V. We prove that every k-hypertournament on n (k) vertices has a Hamiltonian path (an extension of Redeis theorem on tournaments) and every strong k-hypertournament with n (k + 1) vertices has a Hamiltonian cycle (an extension of Camions theorem on tournaments). Despite the last result, it is shown that the Hamiltonian cycle problem remains polynomial time solvable only for k ≤ 3 and becomes NP-complete for every fixed integer k ≥ 4. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 277–286, 1997     

Structure theorem for tournaments omitting N5

A finite tournament T is tight if the class of finite tournaments omitting T is well‐quasi‐ordered. We show here that a certain tournament N₅ on five vertices is tight. This is one of the main steps in an exact classification of the tight tournaments, as explained in [10]; the third and final step is carried out in [11]. The proof involves an encoding of the indecomposable tournaments omitting N₅ by a finite alphabet, followed by an application of Kruskal's Tree Theorem. This problem arises in model theory and in computational complexity in a more general form, which remains open: the problem is to give an effective criterion for a finite set {T₁,…,T_k} of finite tournaments to be tight in the sense that the class of all finite tournaments omitting each of T₁,…,T_k is well‐quasi‐ordered. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 165–192, 2003     

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.     

Pentagons and cycle coverings

Let G be a graph of order n ≥ 5k + 2, where k is a positive integer. Suppose that the minimum degree of G is at least ?(n + k)/2?. We show that G contains k pentagons and a path such that they are vertex‐disjoint and cover all the vertices of G. Moreover, if n ≥ 5k + 7, then G contains k + 1 vertex‐disjoint cycles covering all the vertices of G such that k of them are pentagons. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 194–208, 2007     

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.     

A characterization of panconnected graphs satisfying a local ore-type condition

It is well known that a graph G of order p ≥ 3 is Hamilton-connected if d(u) + d(v) ≥ p + 1 for each pair of nonadjacent vertices u and v. In this paper we consider connected graphs G of order at least 3 for which d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| + 1 for any path uwv with uv ∉ E(G), where N(x) denote the neighborhood of a vertex x. We prove that a graph G satisfying this condition has the following properties: (a) For each pair of nonadjacent vertices x, y of G and for each integer k, d(x, y) ≤ k ≤ |V(G)| − 1, there is an x − y path of length k. (b) For each edge xy of G and for each integer k (excepting maybe one k η {3,4}) there is a cycle of length k containing xy. Consequently G is panconnected (and also edge pancyclic) if and only if each edge of G belongs to a triangle and a quadrangle. Our results imply some results of Williamson, Faudree, and Schelp. © 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.     

Color critical hypergraphs with many edges

We show that for all k ≥ 3, r > l ≥ 2 there exists constant c = c(k, r, l) such that for large enough n there exists a k‐color‐critical r‐uniform hypergraph on less than n vertices, having more than cn^l edges, and having no l‐set of vertices occuring in more than one edge. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 56–74, 2006     

Forcing highly connected subgraphs

A theorem of Mader states that highly connected subgraphs can be forced in finite graphs by assuming a high minimum degree. We extend this result to infinite graphs. Here, it is necessary to require not only high degree for the vertices but also high vertex‐degree (or multiplicity) for the ends of the graph, that is, a large number of disjoint rays in each end. We give a lower bound on the degree of vertices and the vertex‐degree of the ends which is quadratic in k, the connectedness of the desired subgraph. In fact, this is not far from best possible: we exhibit a family of graphs with a degree of order 2^k at the vertices and a vertex‐degree of order k log k at the ends which have no k‐connected subgraphs. Furthermore, if in addition to the high degrees at the vertices, we only require high edge‐degree for the ends (which is defined as the maximum number of edge‐disjoint rays in an end), Mader's theorem does not extend to infinite graphs, not even to locally finite ones. We give a counterexample in this respect. But, assuming a lower bound of at least 2k for the edge‐degree at the ends and the degree at the vertices does suffice to ensure the existence (k + 1)‐edge‐connected subgraphs in arbitrary graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 331–349, 2007     

Sur la (-k)-demi-reconstructibilité des tournois finis

Given a tournament T, we define the dual T^* of T by T^*(x,y) = T(y,x). A tournament T′ is hemimorphic to T if it is isomorphic to T or T^*. A tournament defined on n elements is (-k-reconstructible (resp. (-k)-half-reconstructible) if it is determined up to isomorphism (resp. up to hemimorphism), by its restrictions to subsets of (n - k) elements. From [2] follows the (-k)-half-reconstructibility of finite tournaments (with n ≥ (7 + k) elements), for all k > 7. In this Note, we establish the (-k)-half-reconstructibility of finite tournaments (with n ≥ (12 + k) elements), for all k4,5,6. We then connect the problems of the (-3)- and the (−2)-half-reconstruction of these tournaments to two problems (yet open) of reconstruction. Finally, by using counterexamples of P.K. Stockmeyer [14], we show that, generally, the finite tournaments are not (-k)-half-reconstructible.     

Polynomial time recognition and testing of isomorphism of cyclic tournaments

By a tournament is meant an oriented graph any pair of whose vertices is joined by precisely one directed edge; a tournament is cyclic if its automorphism group contains a permutation whose cyclic decomposition consists of a unique cycle containing all vertices. In the present paper we describe an algorithm for recognizing the isomorphism of cyclic tournaments. This algorithm has an arbitrary tournament as input. For this tournament, in polynomial time in the number of its vertices it determines its cyclicity, and when it is cyclic it constructs a canonical form for the tournament and generators of its automorphism group. A procedure which constructs the set of all nonconjugate Hamiltonian permutations for a given permutation group of odd order in polynomial time is of independent interest. The technique of construction of the basic algorithm uses both classical results of the theory of computational complexity with permutation groups and Schur's method of S-rings.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklovaa AN SSSR, Vol. 192, pp. 74–111, 1991.