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.     

Cycles Containing a Given Arc in Regular Multipartite Tournaments

In this paper we prove that if T is a regular n-partite tournament with n≥>6, then each arc of T lies on a k-cycle for k=4,5,…,n. Our result generalizes theorems due to Alspach and Guo respectively.     

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     

Outpaths of arcs in multipartite tournaments

1. IntroductionThroughout the paPer, we use the terminology and notation of [1] and [2]. Let D =(V(D), A(D)) be a digraPh. If xy is an arc of a digraPh D, then we say that x dominatesy, denoted by x - y. More generally, if A and B are two disjoint vertex sets of D such thatevery vertex of A dominates every vertex of B, then we say that A dominates B, denotedby A - B. The outset N (x) of a vertex x is the set of vertices dominated by x in D,and the inset N--(x) is the set of vertices d…     

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     

On Cycles Containing a Given Arc in Regular Multipartite Tournaments

In this paper we prove that if T is a regular n-partite tournament with n≥4, then each arc of T lies on a cycle whose vertices are from exactly κ partite sets for κ=4,5,…,n. Our result, in a sense, generalizes a theorem due to Alspach.     

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.     

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     

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     

On low bound of degree sequences of spanning trees in K-edge-connected graphs

A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A d_k-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, d_T(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d_k-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998     

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     

A reversal index for tournament matrices *

Given a tournament matrix T, its reversal indexi_R (T), is the minimum k such that the reversal of the orientation of k arcs in the directed graph associated with T results in a reducible matrix. We give a formula for i_R (T) in terms of the score vector of T which generalizes a simple criterion for a tournament matrix to be irreducible. We show that i_R (T)≤[(n?1)/2] for any tournament matrix T of order n, with equality holding if and only if T is regular or almost regular, according as n is odd or even. We construct, for each k between 1 and [(n?1)/2], a tournament matrix of order n whose reversal index is k. Finally, we suggest a few problems.     

An odd Furstenberg-Szemerédi theorem and quasi-affine systems

We prove a version of Furstenberg’s ergodic theorem with restrictions on return times. More specifically, for a measure preserving system (X, B, μ,T), integers 0 ≤j <k, andE ⊂X with μ(E) > 0, we show that there existsn ≡ j (modk) with ώ(E ∩T ^-nE ∩T ^-2nE ∩T ^-3nE) > 0, so long asT ^k is ergodic. This result requires a deeper understanding of the limit of some nonconventional ergodic averages and the introduction of a new class of systems, the ‘Quasi-Affine Systems’. This work was partially carried out while the second author was visiting the Université de Marne la Vallée, supported by NSF grant 9804651.     

Unavoidable trees in tournaments

An oriented tree T on n vertices is unavoidable if every tournament on n vertices contains a copy of T. In this paper, we give a sufficient condition for T to be unavoidable, and use this to prove that almost all labeled oriented trees are unavoidable, verifying a conjecture of Bender and Wormald. We additionally prove that every tournament on vertices contains a copy of every oriented tree T on n vertices with polylogarithmic maximum degree, improving a result of Kühn, Mycroft, and Osthus.     

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     

Score sets ink-partite tournaments

The set S of distinct scores (outdegrees) of the vertices of ak-partite tournamentT(X ₁, X₂, ···, X_k) is called its score set. In this paper, we prove that every set of n non-negative integers, except {0} and {0, 1}, is a score set of some 3-partite tournament. We also prove that every set ofn non-negative integers is a score set of somek-partite tournament for everyn ≥k ≥ 2.     

Cycle-pancyclism in tournaments I

LetT be a hamiltonian tournament withn vertices andγ a hamiltonian cycle ofT. In this paper we start the study of the following question: What is the maximum intersection withγ of a cycle of lengthk? This number is denotedf(n, k). We prove that fork in range, 3 ≤k ≤n + 4/2,f(n,k) ≥ k ? 3, and that the result is best possible; in fact, a characterization of the values ofn, k, for whichf(n, k) = k ? 3 is presented. In a forthcoming paper we studyf(n, k) for the case of cycles of lengthk > n + 4/2.     

Rooted Spanning Trees in Tournaments

A tournament of order n is an orientation of a complete graph with n vertices, and is specified by its vertex set V(T) and edge set E(T). A rooted tree is a directed tree such that every vertex except the root has in-degree 1, while the root has in-degree 0. A rooted k-tree is a rooted tree such that every vertex except the root has out-degree at most k; the out-degree of the root can be larger than k. It is well-known that every tournament contains a rooted spanning tree of depth at most 2; and the root of such a tree is also called a king in the literature. This result was strengthened to the following one: Every tournament contains a rooted spanning 2-tree of depth at most 2. We prove that every tournament of order n≥800 contains a spanning rooted special 2-tree in this paper, where a rooted special 2-tree is a rooted 2-tree of depth 2 such that all except possibly one, non-root, non-leaf vertices, have out-degree 2 in the tree. Revised: November 9, 1998     

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.