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.     

An approximate version of Sumner?s universal tournament conjecture

Sumner?s universal tournament conjecture states that any tournament on 2n−2 vertices contains a copy of any directed tree on n vertices. We prove an asymptotic version of this conjecture, namely that any tournament on (2+o(1))n vertices contains a copy of any directed tree on n vertices. In addition, we prove an asymptotically best possible result for trees of bounded degree, namely that for any fixed Δ, any tournament on (1+o(1))n vertices contains a copy of any directed tree on n vertices with maximum degree at most Δ.     

The maximum number of Hamiltonian paths in tournaments

Solving an old conjecture of Szele we show that the maximum number of directed Hamiltonian paths in a tournament onn vertices is at mostc · n ^3/2 · n!/2 ^n–1, wherec is a positive constant independent ofn.Research supported in part by a U.S.A.-Israel BSF grant and by a Bergmann Memorial Grant.     

Edge coloring of hypergraphs and a conjecture of ErdÖs,Faber, Lovász

Call a bypergraphsimple if for any pairu, v of distinct vertices, there is at most one edge incident to bothu andv, and there are no edges incident to exactly one vertex. A conjecture of Erds, Faber and Lovász is equivalent to the statement that the edges of any simple hypergraph onn vertices can be colored with at mostn colors. We present a simple proof that the edges of a simple hypergraph onn vertices can be colored with at most [1.5n-2 colors].This research was partially supported by N.S.F. grant No. MCS-8311422.     

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     

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 Note on Directed Genera of Some Tournaments

An embedding of a digraph in an orientable surface is an embedding as the underlying graph and arcs in each region force a directed cycle. The directed genus is the minimum genus of surfaces in which the digraph can be directed embedded. Bonnington, Conder, Morton and McKenna [J. Combin. Theory Ser. B, 85(2002) 1-20] gave the problem that which tournaments on n vertices have the directed genus ?(n?3)(n?4)/12 ?, the genus of K_n. In this paper, we use the current graph method to show that there exists a tournament, which has the directed genus ?(n?3)(n?4)/12 ?, on n vertices if and only if n ≡ 3 or 7 (mod 12).     

Packing 4-Cycles in Eulerian and Bipartite Eulerian Tournaments with an Application to Distances in Interchange Graphs

We prove that every Eulerian orientation of K_m,n contains arc-disjoint directed 4-cycles, improving earlier lower bounds. Combined with a probabilistic argument, this result is used to prove that every regular tournament with n vertices contains arc-disjoint directed 4-cycles. The result is also used to provide an upper bound for the distance between two antipodal vertices in interchange graphs.Received February 6, 2004     

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.     

Upper Bounds for Erdös–Hajnal Coefficients of Tournaments

A celebrated unresolved conjecture of Erdös and Hajnal (see Discrete Appl Math 25 (1989), 37–52) states that for every undirected graph H, there exists , such that every graph on n vertices which does not contain H as an induced subgraph contains either a clique or an independent set of size at least . In (Combinatorica (2001), 155–170), Alon et al. proved that this conjecture was equivalent to a similar conjecture about tournaments. In the directed version of the conjecture cliques and stable sets are replaced by transitive subtournaments. For a fixed undirected graph H, define to be the supremum of all ε for which the following holds: for some n₀ and every every undirected graph with vertices not containing H as an induced subgraph has a clique or independent set of size at least . The analogous definition holds if H is a tournament. We call the Erdös–Hajnal coefficient of H. The Erdös–Hajnal conjecture is true if and only if for every H. We prove in this article that:

• the Erdös–Hajnal coefficient of every graph H is at most ,
• there exists such that the Erdös–Hajnal coefficient of almost every tournament T on k vertices is at most , i.e. the proportion of tournaments on k vertices with the coefficient exceeding goes to 0 as k goes to infinity.

     

Solution of a conjecture of Volkmann on longest paths through an arc in strongly connected in‐tournaments

An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. Let m = 4 or m = 5 and let D be a strongly connected in‐tournament of order such that each arc belongs to a directed path of order at least m. In 2000, Volkmann showed that if D contains an arc e such that the longest directed path through e consists of exactly m vertices, then e is the only arc of D with that property. In this article we shall see that this proposition is true for , thereby validating a conjecture of Volkmann. Furthermore, we prove that if we ease the restrictions on the order of D to , the in‐tournament D in question has at most two such arcs. In doing so, we also give a characterization of the in‐tournaments with exactly two such arcs. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 130–148, 2009     

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     

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     

Cycles in weighted graphs

A weighted graph is one in which each edgee is assigned a nonnegative numberw(e), called the weight ofe. The weightw(G) of a weighted graphG is the sum of the weights of its edges. In this paper, we prove, as conjectured in [2], that every 2-edge-connected weighted graph onn vertices contains a cycle of weight at least 2w(G)/(n–1). Furthermore, we completely characterize the 2-edge-connected weighted graphs onn vertices that contain no cycle of weight more than 2w(G)/(n–1). This generalizes, to weighted graphs, a classical result of Erds and Gallai [4].     

A Note on a Packing Problem in Transitive Tournaments

Let TT_n be a transitive tournament on n vertices. We show that for any directed acyclic graph G of order n and of size not greater than two directed graphs isomorphic to G are arc disjoint subgraphs of TT_n. Moreover, this bound is generally the best possible. The research partially supported by KBN grant 2 P03A 016 18     

An erdős—Gallai conjecture

The following conjecture of P. Erdős and T. Gallai is confirmed: every graph onn vertices can be covered byn−1 circuits and edges.     

Graphs of diameter 3 with the minimum number of edges

The graphG is called a porcupine, ifGA is a complete graph for some setA, every other vertex has degree one, and its only edge is joined toA. In this paper a conjecture of Bollobás is settled almost completely. Namely, it is proved that ifG is a graph onn vertices of diameter 3 with maximum degreeD, D > 2.31 ,D (n – 1)/2 and it has the mimimum number of edges, then it is a porcupine.This paper was written while the author visited the Departments of Mathematics, Tel-Aviv University, whose hospitality is gratefully acknowledged.     

Asymptotics for Euclidean minimal spanning trees on random points

Summary Asymptotic results for the Euclidean minimal spanning tree onn random vertices inR ^d can be obtained from consideration of a limiting infinite forest whose vertices form a Poisson process in allR ^d. In particular we prove a conjecture of Robert Bland: the sum of thed'th powers of the edge-lengths of the minimal spanning tree of a random sample ofn points from the uniform distribution in the unit cube ofR ^d tends to a constant asn.Whether the limit forest is in fact a single tree is a hard open problem, relating to continuum percolation.Research supported by N.S.F. Grants MCS87-11426 and MCS 90-01710Research supported in part by N.S.F. Grant DMS88-12868, A.F.O.S.R. Grant 89-0301, ARO Grant DAAL03-89-G-0092 and NSA Grant MDA-904-H-2034     

Hadwiger's Conjecture for the Complements of Kneser Graphs

Hadwiger's conjecture asserts that every graph with chromatic number t contains a complete minor of order t. Given integers , the Kneser graph is the graph with vertices the k‐subsets of an n‐set such that two vertices are adjacent if and only if the corresponding k‐subsets are disjoint. We prove that Hadwiger's conjecture is true for the complements of Kneser graphs.     

Decomposing <Emphasis Type="Italic">k</Emphasis>-ARc-Strong Tournaments Into Strong Spanning Subdigraphs

  The so-called Kelly conjecture states that every regular tournament on 2k+1 vertices has a decomposition into k-arc-disjoint hamiltonian cycles. In this paper we formulate a generalization of that conjecture, namely we conjecture that every k-arc-strong tournament contains k arc-disjoint spanning strong subdigraphs. We prove several results which support the conjecture:If D = (V, A) is a 2-arc-strong semicomplete digraph then it contains 2 arc-disjoint spanning strong subdigraphs except for one digraph on 4 vertices.Every tournament which has a non-trivial cut (both sides containing at least 2 vertices) with precisely k arcs in one direction contains k arc-disjoint spanning strong subdigraphs. In fact this result holds even for semicomplete digraphs with one exception on 4 vertices.Every k-arc-strong tournament with minimum in- and out-degree at least 37k contains k arc-disjoint spanning subdigraphs H ₁, H ₂, . . . , H _k such that each H _i is strongly connected.The last result implies that if T is a 74k-arc-strong tournament with speci.ed not necessarily distinct vertices u ₁, u ₂, . . . , u _k , v ₁, v ₂, . . . , v _k then T contains 2k arc-disjoint branchings where is an in-branching rooted at the vertex u _i and is an out-branching rooted at the vertex v _i , i=1,2, . . . , k. This solves a conjecture of Bang-Jensen and Gutin [3].We also discuss related problems and conjectures.