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.     

Spanning 2-strong tournaments in 3-strong semicomplete digraphs

We prove that every 3-strong semicomplete digraph on at least 5 vertices contains a spanning 2-strong tournament. Our proof is constructive and implies a polynomial algorithm for finding a spanning 2-strong tournament in a given 3-strong semicomplete digraph. We also show that there are infinitely many (2k−2)-strong semicomplete digraphs which contain no spanning k-strong tournament and conjecture that every(2k−1)-strong semicomplete digraph which is not the complete digraph on 2k vertices contains a spanning k-strong tournament.     

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.     

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.     

On monochromatic paths in edge-coloured digraphs

Let G be a directed graph whose edges are coloured with two colours. Call a set S of vertices of Gindependent if no two vertices of S are connected by a monochromatic directed path. We prove that if G contains no monochromatic infinite outward path, then there is an independent set S of vertices of G such that, for every vertex x not in S, there is a monochromatic directed path from x to a vertex of S. In the event that G is infinite, the proof uses Zorn's lemma. The last part of the paper is concerned with the case when G is a tournament.     

Monochromatic sinks in nearly transitive arc-colored tournaments

Let T be the set of all arc-colored tournaments, with any number of colors, that contain no rainbow 3-cycles, i.e., no 3-cycles whose three arcs are colored with three distinct colors. We prove that if T∈T and if each strong component of T is a single vertex or isomorphic to an upset tournament, then T contains a monochromatic sink. We also prove that if T∈T and T contains a vertex x such that T−x is transitive, then T contains a monochromatic sink. The latter result is best possible in the sense that, for each n≥5, there exists an n-tournament T such that (T−x)−y is transitive for some two distinct vertices x and y in T, and T can be arc-colored with five colors such that T∈T, but T contains no monochromatic sink.     

Three supplements to Reid’s theorem in multipartite tournaments

An n-partite tournament is an orientation of a complete n-partite graph. In this paper, we give three supplements to Reid’s theorem [K.B. Reid, Two complementary circuits in two-connected tournaments, Ann. Discrete Math. 27 (1985) 321-334] in multipartite tournaments. The first one is concerned with the lengths of cycles and states as follows: let D be an (α(D)+1)-strong n-partite tournament with n≥6, where α(D) is the independence number of D, then D contains two disjoint cycles of lengths 3 and n−3, respectively, unless D is isomorphic to the 7-tournament containing no transitive 4-subtournament (denoted by ). The second one is obtained by considering the number of partite sets that cycles pass through: every (α(D)+1)-strong n-partite tournament D with n≥6 contains two disjoint cycles which contain vertices from exactly 3 and n−3 partite sets, respectively, unless it is isomorphic to . The last one is about two disjoint cycles passing through all partite sets.     

Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture

We give a short constructive proof of a theorem of Fisher: every tournament contains a vertex whose second outneighborhood is as large as its first outneighborhood. Moreover, we exhibit two such vertices provided that the tournament has no dominated vertex. The proof makes use of median orders. A second application of median orders is that every tournament of order 2n − 2 contains every arborescence of order n > 1. This is a particular case of Sumner's conjecture: every tournament of order 2n − 2 contains every oriented tree of order n > 1. Using our method, we prove that every tournament of order (7n − 5)/2 contains every oriented tree of order n. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 244–256, 2000     

Every cycle-connected multipartite tournament has a universal arc

A digraph D is cycle-connected if for every pair of vertices u,v∈V(D) there exists a directed cycle in D containing both u and v. In 1999, Ádám [A. Ádám, On some cyclic connectivity properties of directed graphs, Acta Cybernet. 14 (1) (1999) 1-12] posed the following problem. Let D be a cycle-connected digraph. Does there exist a universal arc in D, i.e., an arc e∈A(D) such that for every vertex w∈V(D) there is a directed cycle in D containing both e and w?A c-partite or multipartite tournament is an orientation of a complete c-partite graph. Recently, Hubenko [A. Hubenko, On a cyclic connectivity property of directed graphs, Discrete Math. 308 (2008) 1018-1024] proved that each cycle-connected bipartite tournament has a universal arc. As an extension of this result, we show in this note that each cycle-connected multipartite tournament has a universal arc.     

Cycles with a given number of vertices from each partite set in regular multipartite tournaments

If x is a vertex of a digraph D, then we denote by d ⁺(x) and d ⁻(x) the outdegree and the indegree of x, respectively. A digraph D is called regular, if there is a number p ∈ ℕ such that d ⁺(x) = d ⁻(x) = p for all vertices x of D. A c-partite tournament is an orientation of a complete c-partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether c-partite tournaments with r vertices in each partite set contain a cycle with exactly r − 1 vertices of every partite set. In 1982, Beineke and Little [2] solved this problem for the regular case if c = 2. If c ⩾ 3, then we will show that a regular c-partite tournament with r ⩾ 2 vertices in each partite set contains a cycle with exactly r − 1 vertices from each partite set, with the exception of the case that c = 4 and r = 2.     

On cycles in regular 3-partite tournaments

The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph. In 1991, Jian-zhong Wang conjectured that every arc of a regular 3-partite tournament D is contained in directed cycles of all lengths 3,6,9,…,|V(D)|. This conjecture is not valid, because for each integer t with 3?t?|V(D)|, there exists an infinite family of regular 3-partite tournaments D such that at least one arc of D is not contained in a directed cycle of length t.In this paper, we prove that every arc of a regular 3-partite tournament with at least nine vertices is contained in a directed cycle of length m, m+1, or m+2 for 3?m?5, and we conjecture that every arc of a regular 3-partite tournament is contained in a directed cycle of length m, (m+1), or (m+2) for each m∈{3,4,…,|V(D)|-2}.It is known that every regular 3-partite tournament D with at least six vertices contains directed cycles of lengths 3, |V(D)|-3, and |V(D)|. We show that every regular 3-partite tournament D with at least six vertices also has a directed cycle of length 6, and we conjecture that each such 3-partite tournament contains cycles of all lengths 3,6,9,…,|V(D)|.     

Tournois sans intervalle acyclique

An interval X of a tournament T is a vertex subset of T such that any vertex not in X either dominates or is dominated by all of the vertices in X. We caracterize the tournaments such that the only non empty acyclic intervals are the singletons and which are critical for that property, that is whenever a vertex is removed at least one acyclic interval with more than 2 vertices is created. These tournaments are exactly those which are the composition of any tournament with circulant tournaments. That work on acyclic intervals was motivated by the study of tournaments for which no median order forced itself naturally. To cite this article: J.-F. Culus, B. Jouve, C. R. Acad. Sci. Paris, Ser. I 341 (2005).     

Almost all triple systems with independent neighborhoods are semi-bipartite

The neighborhood of a pair of vertices u, v in a triple system is the set of vertices w such that uvw is an edge. A triple system H is semi-bipartite if its vertex set contains a vertex subset X such that every edge of H intersects X in exactly two points. It is easy to see that if H is semi-bipartite, then the neighborhood of every pair of vertices in H is an independent set. We show a partial converse of this statement by proving that almost all triple systems with vertex sets [n] and independent neighborhoods are semi-bipartite. Our result can be viewed as an extension of the Erd?s-Kleitman-Rothschild theorem to triple systems.The proof uses the Frankl-Rödl hypergraph regularity lemma, and stability theorems. Similar results have recently been proved for hypergraphs with various other local constraints.     

On well-covered triangulations: Part III

A graph G is said to be well-covered if every maximal independent set of vertices has the same cardinality. A planar (simple) graph in which each face is a triangle is called a triangulation. It was proved in an earlier paper Finbow et al. (2004) [3] that there are no 5-connected planar well-covered triangulations, and in Finbow et al. (submitted for publication) [4] that there are exactly four 4-connected well-covered triangulations containing two adjacent vertices of degree 4. It is the aim of the present paper to complete the characterization of 4-connected well-covered triangulations by showing that each such graph contains two adjacent vertices of degree 4.     

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     

Sur la répartition des diamants dans un tournoi

A tournament T=(V,A) is a directed graph such that for every x,y∈V, where x≠y, (x,y)∈A if and only if (y,x)?A. For example, the 3-cycle is the tournament ({1,2,3}, {(1,2),(2,3),(3,1)}). Up to an isomorphism, there are two tournaments with 4 vertices and containing an unique 3-cycle which we call diamonds. We prove that for any tournament T defined on n?9 vertices, either T contains at least 2n?6 diamonds or the number of diamonds contained in T is equal to 0, n?3 or 2n?8. Following the characterization of the tournaments without diamonds due to Gnanvo and Ille (Z. Math. Logik Grundlag. Math. 38 (1992) 283–291) and to Lopez and Rauzy (Z. Math. Logik Grundlag. Math. 38 (1992) 27–37), we study the morphology of the tournaments defined on n?5 vertices and which contain exactly n?3 or 2n?8 diamonds. To cite this article: H. Bouchaala, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Monochromatic Paths and at Most 2-Coloured Arc Sets in Edge-Coloured Tournaments

We call the tournament T an m-coloured tournament if the arcs of T are coloured with m-colours. If v is a vertex of an m-coloured tournament T, we denote by ξ(v) the set of colours assigned to the arcs with v as an endpoint. In this paper is proved that if T is an m-coloured tournament with |ξ(v)|≤2 for each vertex v of T, and T satisfies at least one of the two following properties (1) m≠3 or (2) m=3 and T contains no C₃ (the directed cycle of length 3 whose arcs are coloured with three distinct colours). Then there is a vertex v of T such that for every other vertex x of T, there is a monochromatic directed path from x to v. Received: April, 2003     

On arc-traceable local tournaments

A digraph D is arc-traceable if for every arc xy of D, the arc xy belongs to a directed Hamiltonian path of D. A local tournament is an oriented graph such that the negative neighborhood as well as the positive neighborhood of every vertex induces a tournament. It is well known that every tournament contains a directed Hamiltonian path and, in 1990, Bang-Jensen showed the same for connected local tournaments. In 2006, Busch, Jacobson and Reid studied the structure of tournaments that are not arc-traceable and consequently gave various sufficient conditions for tournaments to be arc-traceable. Inspired by the article of Busch, Jacobson and Reid, we develop in this paper the structure necessary for a local tournament to be not arc-traceable. Using this structure, we give sufficient conditions for a local tournament to be arc-traceable and we present examples showing that these conditions are best possible.