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.     

Degree and local connectivity in digraphs

It is shown that there is a digraphD of minimum outdegree 12m and μ(x, y; D)=11m, but every digraphD of minimum outdegreen contains verticesx ≠y withλ(x, y; D)≧n−1, whereμ(x, y; D) andλ(x, y; D) denote the maximum number of openly disjoint and edge-disjoint paths, respectively.     

Locally semicomplete digraphs: A generalization of tournaments

In this paper we introduce a new class of directed graphs called locally semicomplete digraphs. These are defined to be those digraphs for which the following holds: for every vertex x the vertices dominated by x induce a semicomplete digraph and the vertices that dominate x induce a semicomplete digraph. (A digraph is semicomplete if for any two distinct vertices u and ν, there is at least one arc between them.) This class contains the class of semicomplete digraphs, but is much more general. In fact, the class of underlying graphs of the locally semi-complete digraphs is precisely the class of proper circular-arc graphs (see [13], Theorem 3). We show that many of the classic theorems for tournaments have natural analogues for locally semicomplete digraphs. For example, every locally semicomplete digraph has a directed Hamiltonian path and every strong locally semicomplete digraph has a Hamiltonian cycle. We also consider connectivity properties, domination orientability, and algorithmic aspects of locally semicomplete digraphs. Some of the results on connectivity are new, even when restricted to semicomplete digraphs.     

Degree sets for digraphs

The degree setD _D of a digraphD is the set of outdegrees of the vertices ofD. For a finite, nonempty setS of nonnegative integers, it is shown that there exists an asymmetric digraph (oriented graph)D such thatD _D =S. Furthermore, the minimum order of such a digraphD is determined. Also, given two finite sequences of nonnegative integers, a necessary and sufficient condition is provided for which these sequences are the outdegree sequences of the two sets of an asymmetric bipartite digraph.     

Hall exponents of matrices,tournaments and their line digraphs

Let A be a square (0, 1)-matrix. Then A is a Hall matrix provided it has a nonzero permanent. The Hall exponent of A is the smallest positive integer k, if such exists, such that A ^k is a Hall matrix. The Hall exponent has received considerable attention, and we both review and expand on some of its properties. Viewing A as the adjacency matrix of a digraph, we prove several properties of the Hall exponents of line digraphs with some emphasis on line digraphs of tournament (matrices).     

On topological tournaments of order 4 in digraphs of outdegree 3

It is proved that every finite digraph of minimum outdegree 3 contains a subdivision of the transitive tournament on 4 vertices. © 1996 John Wiley & Sons, Inc.     

Degree sum conditions for oriented forests in digraphs

Let F be an oriented forest with n vertices and m arcs and D be a digraph without loops and multiple arcs. In this note we prove that D contains a subdigraph isomorphic to F if D has at least n vertices and min{d⁺(u)+d⁺(v),d⁻(u)+d⁻(v),d⁺(u)+d⁻(v)}≥2m−1 for every pair of vertices u,v∈V(D) with uv∉A(D). This is a common generalization of two results of Babu and Diwan, one on the existence of forests in graphs under a degree sum condition and the other on the existence of oriented forests in digraphs under a minimum degree condition.     

The asymptotic numbers of regular tournaments,Eulerian digraphs and Eulerian oriented graphs

LetRT(n), ED(n) andEOG(n) be the number of labelled regular tournaments, labelled loop-free simple Eulerian digraphs, and labelled Eulerian oriented simple graphs, respectively, onn vertices. Then, asn,, for any>0. The last two families of graphs are also enumerated by their numbers of edges. The proofs use the saddle point method applied to appropriaten-dimensional integrals.     

Degree sequence conditions for maximally edge-connected graphs and digraphs

In this paper we give simple degree sequence conditions for the equality of edge-connectivity and minimum degree of a (di-)graph. One of the conditions implies results by Bollobás, Goldsmith and White, and Xu. Moreover, we give analogue conditions for bipartite (di-)graphs. © 1997 John Wiley & Sons, Inc. J Graph Theory 26:27–34, 1997     

Connection digraphs and second-order line digraphs

The primary result of this paper gives a set of necessary and sufficient conditions for a digraph to be second-order line digraph of some digraph. A directed analogue of the concept of an intersection graph, defined for collections of ordered pairs of sets and called the connection digraph, is used to achieve this result.     

On super-edge-connected digraphs and bipartite digraphs

A maximally edge-connected digraph is called super-λ if every minimum edge disconnecting set is trivial, i.e., it consists of the edges adjacent to or from a given vertex. In this paper sufficient conditions for a digraph to be super-λ are presented in terms of parameters such as diameter and minimum degree. Similar results are also given for bipartite digraphs. As a corollary, some characterizations of super-λ graphs and bipartite graphs are obtained. © 1929 John Wiley & Sons, Inc.     

Degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number

Let $D$ be a finite and simple digraph with vertex set $V\left(D\right)$. For a vertex $v\in V\left(D\right)$, the degree $d\left(v\right)$ of $v$ is defined as the minimum value of its out-degree $d^{+}\left(v\right)$ and its in-degree $d^{?}\left(v\right)$. If $D$ is a graph or a digraph with minimum degree $\delta$ and edge-connectivity $\lambda$, then $\lambda \le \delta$. A graph or a digraph is maximally edge-connected if $\lambda =\delta$. A graph or a digraph is called super-edge-connected if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree.In this note we present degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number of the underlying graph.     

Trees in tournaments

Letf(n) be the smallest integer such that every tournament of orderf(n) contains every oriented tree of ordern. Sumner has just conjectures thatf(n)=2n–2, and F. K. Chung has shown thatf(n)(1+o(1))nlog₂ n. Here we show thatf(n)12n andf(n)(4+o(1))n.     

Independent sets and non-augmentable paths in arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs

A digraph is arc-locally in-semicomplete if for any pair of adjacent vertices x,y, every in-neighbor of x and every in-neighbor of y either are adjacent or are the same vertex. A digraph is quasi-arc-transitive if for any arc xy, every in-neighbor of x and every out-neighbor of y either are adjacent or are the same vertex. Laborde, Payan and Xuong proposed the following conjecture: Every digraph has an independent set intersecting every non-augmentable path (in particular, every longest path). In this paper, we shall prove that this conjecture is true for arc-locally in-semicomplete digraphs and quasi-arc-transitive digraphs.     

Cycle-pancyclism in tournaments II

LetT be a Hamiltonian tournament withn vertices and a Hamiltonian cycle ofT. In this paper we develope a general method to find cycles of lengthk, n+4/2 < k < n, intersecting in a large number of arcs. In particular we can show that if there does not exist a cycle.C _k intersecting in at leastk – 3 arcs then for any arce of there exists a cycleC _k containinge and intersecting in at leastk – 2(n–3)/n–k+3 – 2 arcs. In a previous paper [3] the case of cycles of lengthk, k n+4/2 was studied.On leave at MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, USA.     

Weakening arcs in tournaments

A weakening arc of an irreducible tournament is an arc whose reversal creates a reducible tournament. We consider properties of such arcs and derive recurrence relations for enumerating strong tournaments with no such arcs, one or more such arcs, and exactly one such arc. We also give some asymptotic results on the numbers of such tournaments, among other things. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 142–162, 2004     

Disjoint paths in tournaments

Given k   pairs of vertices (_si,_ti)$(s_i,t_i)$(1≤i≤k)$(1\le i\le k)$ of a digraph G, how can we test whether there exist k   vertex-disjoint directed paths from _si$s_i$ to _ti$t_i$ for 1≤i≤k$1\le i\le k$? This is NP-complete in general digraphs, even for k=2$k=2$ [2], but for k=2$k=2$ there is a polynomial-time algorithm when G is a tournament (or more generally, a semicomplete digraph), due to Bang-Jensen and Thomassen [1]. Here we prove that for all fixed k there is a polynomial-time algorithm to solve the problem when G is semicomplete.