Linkedness and ordered cycles in digraphs
LINKEDNESS AND ORDERED CYCLES IN DIGRAPHS
DANIELA KÜHN AND DERYK OSTHUS
Abstract. Given a digraph D, let δ(D) := min{δ+(D), δ−(D)} be the min-
imum degree of D. We show that every sufficiently large digraph D with
δ(D) ≥ n/2 + ℓ − 1 is ℓ-linked. The bound on the minimum degree is best
possible and confirms a conjecture of Manoussakis [16]. We also determine the
smallest minimum degree which ensures that a sufficiently large digraph D is
k-ordered, i.e. that for every sequence s1, . . . , sk of distinct vertices of D there
is a directed cycle which encounters s1, . . . , sk in this order.
1. Introduction
The minimum degree δ(D) of a digraph D is the minimum of its minimum
outdegree δ+(D) and its minimum indegree δ−(D). When referring to paths and
cycles in digraphs we always mean that these are directed without mentioning
this explicitly. A digraph D is ℓ-linked if |D| ≥ 2ℓ and if for every sequence
x1, . . . , xℓ, y1, . . . , yℓ of distinct vertices there are disjoint paths P1, . . . , Pℓ in D
such that Pi joins xi to yi. Since this is a very strong and useful property to have
in a digraph, the question of course arises how it can be forced by other properties.
In the case of (undirected) graphs, much progress has been made in this di-
rection. In particular, linkedness is closely related to connectivity: Bollobás and
Thomason [2] showed that every 22k-connected graph is k-linked (this was recently
improved to 10k by Thomas and Wollan [17]). However, for digraphs the situa-
tion is quite different: Thomassen [18] showed that for all k there are strongly
k-connected digraphs which are not even 2-linked.
Our first result determines the minimum degree forcing a (large) digraph to be
ℓ-linked, which confirms a conjecture of Manoussakis [16] for large digraphs.
Theorem 1. Let ℓ ≥ 2. Every digraph D of order n ≥ 1600ℓ3 which satisfies
δ(D) ≥ n/2 + ℓ− 1 is ℓ-linked.
It is not hard to see that the bound on minimum degree in Theorem 1 is best
possible (see Proposition 3). It is also easy to see that for ℓ = 1 the correct bound
is δ(D) ≥ ⌊n/2⌋. The cases ℓ = 2, 3 of Theorem 1 were proved by Heydemann and
Sotteau [9] and Manoussakis [16] respectively. Manoussakis [16] also determined
the number of edges which force a digraph to be ℓ-linked. A discussion of these
and related results can be found in the monograph by Bang-Jensen and Gutin [1].
Note that it does not make sense to ask for the minimum outdegree of a di-
graph D which ensures that D is ℓ-linked (or similarly, to ask for the minimum
indegree). Indeed, the digraph obtained from a complete digraph A of order n− 1
by adding a new vertex x which sends an edge to every vertex in A has minimum
outdegree n− 2 but is not even 1-linked.
A slightly weaker notion is that of a k-ordered digraph: a digraph D is k-ordered
if |D| ≥ k and if for every sequence s1, . . . , sk of distinct vertices ofD there is a cycle
http://arxiv.org/abs/0704.0211v1
2 DANIELA KÜHN AND DERYK OSTHUS
which encounters s1, . . . , sk in this order. It is not hard to see that every ℓ-linked
digraph is also ℓ-ordered. Conversely, every 2ℓ-ordered digraph D is also ℓ-linked:
if x1, . . . , xℓ, y1, . . . , yℓ is a sequence of vertices as in the definition of ℓ-linkedness
then a cycle which encounters x1, y1, x2, y2, . . . , xℓ, yℓ in this order would yield the
paths required for the linking. The next result says that as far as the minimum
degree is concerned it is no harder to guarantee the 2ℓ paths forming such a cycle
than to guarantee just the ℓ paths required for the linking. In particular, note that
Theorem 2 immediately implies Theorem 1.
Theorem 2. Let k ≥ 2. Every digraph D of order n ≥ 200k3 which satisfies
δ(D) ≥ (n+ k)/2 − 1 is k-ordered.
Again, the bound on the minimum degree is best possible (see Proposition 4).
Moreover, it is easy to see that if k = 1 then the correct bound is δ(D) ≥ n/2− 1.
The proof of Theorem 2 yields paths between the k ‘special’ vertices whose length
is at most 6 and it is also easy to translate the proof into an algorithm which finds
these paths in polynomial time (see the remarks after the end of the proof).
Somewhat surprisingly, the minimum degree in both theorems is not quite the
same as in the undirected case: Kawarabayashi, Kostochka and Yu [12] proved
that the smallest minimum degree which guarantees a graph on n vertices to be
ℓ-linked is ⌊n/2⌋ + ℓ − 1 for large n. (Egawa et al. [4] independently determined
the smallest minimum degree which guarantees the existence of ℓ disjoint cycles
containing ℓ specified independent edges, which is clearly a very similar property.)
Kierstead, Sarközy and Selkow [13] proved that the smallest minimum degree which
guarantees a graph on n vertices to be k-ordered is δ(D) ≥ ⌈n/2⌉ + ⌊k/2⌋ − 1 for
large n. So in the undirected case the ‘2ℓ-ordered’ result does not quite imply the
‘ℓ-linked’ result. The proofs in [4, 12, 13] do not seem to generalize to digraphs.
2. Further work and open problems
In a sequel to this paper, we hope to apply Theorem 2 to obtain the following
stronger results, which would also generalize the theorem of Ghouila-Houri [6] that
any digraph D on n vertices with δ(D) ≥ n/2 contains a Hamilton cycle: we aim
to apply Theorem 2 to show that if k ≥ 2 and D is a sufficiently large digraph
whose minimum degree is as in Theorem 2 then D is even k-ordered Hamiltonian,
i.e. for every sequence s1, . . . , sk of distinct vertices of D there is a Hamilton cycle
which encounters s1, . . . , sk in this order. One can use this to prove that the
minimum degree condition in Theorem 1 already implies that the digraph D is
Hamiltonian ℓ-linked, i.e. the paths linking the pairs of vertices span the entire
vertex set of D. Note that this in turn would immediately imply that D is ℓ-arc
ordered Hamiltonian, i.e. D has a Hamilton cycle which contains any ℓ disjoint
edges in a given order. Note that in each case the examples in Section 3 show
that the minimum degree condition would be best possible. Undirected versions
of these statements were first obtained by Kierstead, Sarközy and Selkow [13] and
Egawa et al. [4] respectively (and a common generalization of these in [3]).
For graphs, the concepts ‘ℓ-linked’ and ‘k-ordered’ were generalized to ‘H-linked’
by Jung [11]: a graph G isH-linked ifG contains a subdivision ofH with prescribed
branch vertices (so G is k-ordered if and only if it is Ck-linked). The minimum
LINKEDNESS AND ORDERED CYCLES IN DIGRAPHS 3
degree which forces a graph to be H-linked for an arbitrary H was determined
in [5, 14, 15, 7]. Clearly, one can ask similar questions also for digraphs.
Finally, we believe that the bound on n which we require in Theorem 2 (and
thus in Theorem 1) can be reduced to one which is linear in k.
3. Notation and extremal examples
Before we discuss the examples showing that the bounds on the minimum degree
in Theorems 1 and 2 are best possible, we will introduce the basic notation used
throughout the paper. A digraph D is complete if every pair of vertices of D is
joined by edges in both directions. The order |D| of a digraph D is the number of
its vertices. We write N+(x) for the outneighbourhood of a vertex x and d+(x) :=
|N+(x)| for its outdegree. Similarly, we write N−(x) for the inneighbourhood of a
vertex x and d−(x) := |N−(x)| for its indegree. We set d(x) := min{d+(x), d−(x)}.
Given a set A of vertices of D, we write N+
(x) for the set of all outneighbours
of x in A. N−
(x), d+
(x) and d−
(x) are defined similarly. Given two vertices x, y
of a digraph D, an x-y path in D is a directed path which joins x to y. Given two
disjoint vertex sets A and B of D, an A-B edge is an edge
ab where a ∈ A and
b ∈ B.
The following proposition shows that the bound on the minimum degree in
Theorem 1 cannot be reduced.
Proposition 3. For every ℓ ≥ 2 and every n ≥ 2ℓ there exists a digraph D on n
vertices with minimum degree ⌈n/2⌉+ ℓ− 2 which is not ℓ-linked.
Proof. We will distinguish the following cases.
Case 1. n is even.
Let D be the digraph which consists of complete digraphs A and B of order n/2+
ℓ − 1 which have precisely 2ℓ − 2 vertices in common. To see that D is not ℓ-
linked let x1, . . . , xℓ−1, y1, . . . , yℓ−1 denote the vertices in A∩B. Pick some vertex
xℓ ∈ A \ B and some vertex yℓ ∈ B \ A. Then D does not contain disjoint paths
between xi and yi for all i = 1, . . . , ℓ. The minimum degree of D is attained by
the vertices in (A \B) ∪ (B \A) and thus is as desired.
Case 2. n is odd.
In this case, we define D as follows. Let A and B be disjoint complete digraphs
of order ⌈n/2⌉ − ℓ − 1. Add a complete digraph X of order 2ℓ − 3 and join all
vertices in X to all vertices in A ∪ B with edges in both directions. Add a set
S := {x1, x2, y1, y2} of 4 new vertices such that each vertex in S is joined to each
vertex in X with edges in both directions. Moreover, we add all the edges between
different vertices in S except for −−→x1y1 and
−−→x2y2. Finally, we connect the vertices
in S to the vertices in A ∪ B as follows. Both x1 and y1 receive edges from every
vertex in B and send edges to every vertex in A. Additionally, x1 will receive an
edge from every vertex in A and y1 will send an edge to every vertex in B. Both x2
and y2 receive edges from every vertex in A and send edges to every vertex in B.
Additionally, x2 will receive an edge from every vertex in B and y2 will send an
edge to every vertex in A (see Figure 1).
To check that D has the required minimum degree, consider first any vertex a ∈
A. As a sends edges to 3 vertices in S and receives edges from 3 such vertices,
4 DANIELA KÜHN AND DERYK OSTHUS
PSfrag replacements
Figure 1. The digraph D in Case 2 of Proposition 3. The dashed
arrows indicate the missing edges between x1 and y1 and between x2
and y2.
we have that d(a) = |A| − 1 + |X| + 3 = ⌈n/2⌉ + ℓ − 2. It follows similarly
that the vertices in B have the correct degree. Thus consider any vertex s ∈ S.
Then s sends edges to all vertices in A or to all vertices in B (or both) and s
receives edges from all vertices in A or from all vertices in B (or both). Thus
d(s) = |A| + |X| + 2 = ⌈n/2⌉ + ℓ − 2. It is easy to check that the vertices in X
have the required degree and thus δ(D) = ⌈n/2⌉+ ℓ− 2.
To see that D is not ℓ-linked, let x, x3, . . . , xℓ, y3, . . . , yℓ denote the vertices
in X. Then we cannot link xi to yi for each i = 1, . . . , ℓ since every x1-y1 path
must meet X ∪ {x2, y2} (and thus would contain x) and the analogue is true for
every x2-y2 path. �
We conclude this section with the examples showing that the bound on the
minimum degree in Theorem 2 is best possible.
Proposition 4. For every k ≥ 2 and every n ≥ 2k there exists a digraph D on n
vertices with minimum degree ⌈(n+ k)/2⌉ − 2 which is not k-ordered.
Proof. We will distinguish the following cases.
Case 1. k ≥ 3 is odd and n is even.
In this case, we define D as follows. Let A and B be disjoint complete digraphs
of order n/2 − k + 1. Add a complete digraph X of order k − 2 and join all its
vertices to all vertices in A ∪ B with edges in both directions. Add new vertices
s1, . . . , sk such that every si is joined to all vertices in X with edges in both
directions. Moreover, we add all the edges −−→sisj for j 6= i, i + 1 where sk+1 := s1.
We also add the edge −−→s1s2. Finally, we connect the si to the vertices in A ∪ B
as follows. Both s1 and s2 receive edges from every vertex in B and send edges
to every vertex in B. Additionally, s1 will send an edge to every vertex in A and
s2 will receive an edge from every vertex in A. Each of s3, s5, . . . , sk receives an
edge from every vertex in A and sends an edge to every vertex in A. Each of
s4, s6, . . . , sk−1 receives an edge from every vertex in B and sends an edge to every
vertex in B (see Figure 2). Let us now check that the minimum degree of the
digraph D thus obtained is as required. Let S := {s1, . . . , sk}. Note that each
LINKEDNESS AND ORDERED CYCLES IN DIGRAPHS 5
PSfrag replacements
Figure 2. The digraph D for k = 5 in Case 1 of Proposition 4.
The dashed arrows indicate missing edges between the vertices si.
vertex v ∈ A ∪ B sends edges to precisely (k + 1)/2 vertices in S and receives
edges from precisely that many vertices. Since |A| = |B|, it follows that d(v) =
|A| − 1 + |X|+ (k + 1)/2 = n/2− 2 + (k + 1)/2 = ⌈(n + k)/2⌉ − 2. Now consider
any si ∈ S. Then si receives edges from either all vertices in A or all vertices in B
(or both) and si sends edges to either all vertices in A or all vertices in B (or both).
Hence d(si) ≥ |A|+ |X| + |S| − 2 = n/2− 1 + k − 2 ≥ ⌈(n + k)/2⌉ − 2. It is easy
to check that the degree of the vertices in X is > ⌈(n+ k)/2⌉ − 2.
To see that D is not k-ordered note that every cycle in D which encounters
s1, . . . , sk in this order would use at least one vertex from X between si and si+1
for every i 6= 1 (see Figure 2). But since |X| = k − 2 this is impossible.
Case 2. k is even.
LetD be the digraph which consists of a complete digraph A of order ⌈n/2⌉+k/2−1
and a complete digraph B of order ⌊n/2⌋+ k/2 which has precisely k − 1 vertices
in common with A. It is easy to check that δ(D) = |A| − 1 = ⌈(n + k)/2⌉ − 2. To
see that D is not k-ordered, pick vertices s1, s3, . . . , sk−1 in A\B and s2, s4, . . . , sk
in B \ A. Then every cycle in D which encounters s1, . . . , sk in this order would
meet A∩B when going from si to si+1, i.e. it would meet A∩B k times, which is
impossible.
Case 3. k ≥ 3 is odd and n is odd.
This time we take D to be the digraph which consists of two complete digraphs A
and B of order (n + k)/2 − 1 having k − 2 vertices in common. Then δ(D) =
|A| − 1 = (n+ k)/2− 2. To see that D is not k-ordered, pick vertices s1, s3, . . . , sk
in A \B and s2, s4, . . . , sk−1 in B \ A. �
Note that in the proof of Proposition 4 we could have omitted the (easy) case
when k is even as Proposition 3 already gives a digraph of the required minimum
degree which is not k/2-linked and thus not k-ordered.
6 DANIELA KÜHN AND DERYK OSTHUS
4. Proof of Theorem 2
We first prove Theorem 2 for the case when k = 2. So suppose that D is a
digraph of minimum degree at least ⌈n/2⌉. Let s1 and s2 be the vertices which
our cycle has to encounter. If −−→s1s2 is not an edge then s1, s2 /∈ N
+(s1) ∪ N
−(s2)
and so |N+(s1) ∩N
−(s2)| ≥ 2δ(D) − (n− 2) ≥ 2. Similarly, if
−−→s2s1 is not an edge
then |N−(s1) ∩N
+(s2)| ≥ 2. Altogether this shows that there is a cycle of length
at most 4 which contains both s1 and s2.
Thus we may assume that k ≥ 3 and that D is a digraph of minimum degree
at least ⌈(n + k)/2⌉ − 1. Let S := (s1, . . . , sk) be the given sequence of vertices
of D which our cycle has to encounter. We will call these vertices special and will
sometimes also use S for the set of these vertices. We set sk+1 := s1. Given a set
I ⊆ [k] and a family T := (ti)i∈I of positive integers, an (S, I, T )-system is a family
(Pi)i∈I where each Pi is a set of ti paths joining si to si+1 and each path in Pi
has length at most 6 and is internally disjoint from S, from all other paths in Pi
and from the paths in all the other Pj . An (S, I)-system is an (S, I, T )-system
where ti = 1 for all i ∈ I. Thus to prove Theorem 2 we have to show that there
exists an (S, [k])-system.
Let I be the set of all those indices i ∈ [k] for which D does not contain at
least 6k internally disjoint si-si+1 paths of length at most 6.
Claim 1. It suffices to show that D contains an (S, I)-system.
Indeed, suppose that (Pi)i∈I is an (S, I)-system in D. So each Pi contains precisely
one path Pi. We will show that for every i ∈ [k]\I we can find an si-si+1 path Pi of
length at most 6 which meets S only in si and si+1 such that all the paths P1, . . . , Pk
are internally disjoint. We will choose such a path Pi for every i ∈ [k] \ I in turn.
Suppose that next we want to find Pj . Recall that since j ∈ [k] \ I the digraph D
contains a set P of at least 6k internally disjoint sj-sj+1 paths of length at most 6.
Since at most 5(k − 1) + k < 6k vertices of D lie in S or in the interior of some of
the other paths Pi, one of the paths in P must be internally disjoint from S and
all the other paths Pi, and so we can take this path to be Pj . This proves Claim 1.
In order to prove the existence of an (S, I)-system, choose an (S, J, T )-system
(Pj)j∈J in D such that J ⊆ I is as large as possible and subject to this
j∈J tj is
maximal. Note that tj < 6k for all j ∈ J since J ⊆ I. Assume that |J | < |I|. By
relabelling the special vertices, we may assume that k ∈ I \ J . So we would like
to extend (Pj)j∈J by a suitable sk-s1 path. Let X
′ be the set of all those vertices
which lie in the interior of some path belonging to (Pj)j∈J . Note that
|S ∪X ′| < 6k · 5(k − 1) + |S| < 30k2 =: k0.
Let A := N+(sk) \ (S ∪X
′) and B := N−(s1) \ (S ∪X
′). Then
(1) |A|, |B| ≥ δ(D) − |S ∪X ′| ≥ n/2− k0.
Moreover, A ∩ B = ∅ as otherwise we could extend our (S, J, T )-system (Pj)j∈J
by adding the path Pk := skxs1 where x ∈ A ∩B, a contradiction to the choice of
(Pj)j∈J . In particular, this shows that the set X
′′ of all vertices outside A ∪ B ∪
S ∪X ′ has size at most 2k0 and thus, setting Y := S ∪X
′ ∪X ′′, we have that
|Y | ≤ 3k0.
LINKEDNESS AND ORDERED CYCLES IN DIGRAPHS 7
Note that D does not contain an edge
ab with a ∈ A and b ∈ B. Indeed, otherwise
we could extend (Pj)j∈J by adding the path Pk := skabs1. We will often use the
following claim.
Claim 2. Let a ∈ A and let A′ ⊆ A be a set of size at least k0. Then N
+(a)∩A′ 6=
∅. Similarly, if b ∈ B and B′ ⊆ B is a set of size at least k0 then N
−(b) ∩B′ 6= ∅.
Suppose that N+(a) ∩ A′ = ∅. Then (1) together with the fact that D does not
contain an A-B edge implies that d+(a) ≤ n − |B| − k0 ≤ n/2, a contradiction.
The proof of the second part of the claim is similar.
We say that a special vertex si has out-type A if si sends at least k0 edges to A.
Similarly we define when si has out-type B, in-type A and in-type B. As |Y |+2k0 ≤
5k0 ≤ δ(G), it follows that each si has out-type A or out-type B (or both) and
in-type A or in-type B (or both). Note that s1 has in-type B but not in-type A
whereas sk has out-type A but not out-type B.
Claim 3. Let j ∈ J . If sj has out-type A then sj+1 has in-type B but not in-type A.
Similarly, if sj has out-type B then sj+1 has in-type A but not in-type B.
Suppose that sj has out-type A and sj+1 has in-type A. Let a ∈ N
(sj). Claim 2
implies that a sends an edge to one of the at least k0 vertices in N
(sj+1). Let
a′ ∈ N−
(sj+1) be such a neighbour of a. Then we could extend our (S, J, T )-
system by adding the path sjaa
′sj+1, a contradiction. The proof of the second
part of Claim 3 is similar.
Claim 4. No vertex in B sends an edge to A.
Suppose that
b∗a∗ is an edge of D, where a∗ ∈ A and b∗ ∈ B. Given vertices
a ∈ A and b ∈ B, put Nab := N
+(a) ∩ N−(b). Note that Nab ⊆ Y and a, b /∈
N+(a) ∪N−(b) as D does not contain an A-B edge. Thus
(2) |Nab| ≥ 2δ(D) − (n− 2) =
− (n− 2) ≥ k.
Let us now show that no special vertex si with i ∈ J has out-type B. So suppose
i ∈ J and si has out-type B. Then Claim 3 implies that si+1 has in-type A. By
Claim 2 some of the at least k0 vertices in N
(si+1) receives an edge from a
∗. Let
a′ be such a vertex. Similarly, some of the vertices in N+
(si) sends an edge to b
Let b′ be such a vertex. Then we could extend our (S, J, T )-system by adding
the path sib
′b∗a∗a′si+1, a contradiction. This shows that whenever si is a special
vertex of out-type B then i /∈ J . Let Q denote the set of such vertices si. Note
that sk 6∈ Q as sk does not have out-type B. Thus each special vertex in Q forbids
one index in J . Altogether this shows that
(3) |J | ≤ k − 1− |Q|.
Let SA be the set of all those special vertices si with 1 ≤ N
(si) < k0. Let SB
be the set of all those special vertices si with 1 ≤ N
(si) < k0. Let A
∗ be the set
of all those vertices in A which do not send an edge to some vertex in SA. Then
|A∗| > |A| − kk0. Similarly, let B
∗ be the set of all those vertices in B which do
not receive an edge from some vertex in SB. Then |B
∗| > |B| − kk0.
8 DANIELA KÜHN AND DERYK OSTHUS
PSfrag replacements
Figure 3. Modifying our (S, J, T )-system in the proof of Claim 4.
Consider any pair a, b with a ∈ A∗ and b ∈ B∗. As each special vertex in Nab
belongs to Q, it follows that
(4) |Nab \ S| ≥ |Nab| − |Q|
≥ k − |Q|
> |J |.
Suppose first that J 6= ∅. Given j ∈ J , let X ′′j be the union of X
′′ with the set
of all vertices lying in the interior of paths in Pj. As Nab ⊆ Y there must be
an index jab ∈ J such that Nab contains at least two vertices in X
. Note that
|A∗|, |B∗| > 2k0k. Thus there are 2k0+1 disjoint pairs a, b for which this index jab
must be the same. Let aq, bq (q = 0, . . . , 2k0) denote these pairs and let j ∈ J
denote the common index.
Note that sj has out-type A since we have seen before that no special vertex si
with i ∈ J has out-type B. Claim 3 now implies that sj+1 has in-type B. Pick
vertices a ∈ N+
(sj) and b ∈ N
(sj+1) such that a 6= a0 and b 6= b0. Claim 2
implies that there are indices q1, . . . , qk0 such that a sends an edge to each aqr .
Apply Claim 2 again to find an index r ≤ k0 such that b receives an edge from bqr .
Let x ∈ Naqr bqr and y ∈ Na0b0 be distinct vertices such that x, y ∈ X
j . We
can now modify our (S, J, T )-system to obtain an (S, J ∪ {k}, T ′)-system in D
by replacing Pj with the single path sjaaqrxbqrbsj+1 and adding the sk-s1 path
ska0yb0s1 (see Figure 3). If J = ∅ then we just add the sk-s1 path (which is still
guaranteed by (4)). In both cases this contradicts the choice of our (S, J, T )-system
and completes the proof of Claim 4.
Claim 5. Let a ∈ A and let A′ ⊆ A be a set of size at least k0. Then N
−(a)∩A′ 6=
∅. Similarly, if b ∈ B and B′ ⊆ B is a set of size at least k0 then N
+(b) ∩B′ 6= ∅.
Using Claim 4, this can be shown similarly as Claim 2.
Let S+
be the set of all those special vertices which send an edge to A and let S−
be the set of all those special vertices which receive an edge from A. Define S+
and S−
similarly. Note that these sets are not disjoint. The proof of the next claim
LINKEDNESS AND ORDERED CYCLES IN DIGRAPHS 9
is similar to that of Claim 3. (To prove the second and third part of Claim 6 we
use Claim 5 instead of Claim 2.)
Claim 6. If j ∈ J and sj ∈ S
then sj+1 cannot have in-type A. If j − 1 ∈ J
and sj ∈ S
then sj−1 cannot have out-type A. If j ∈ J and sj ∈ S
then sj+1
cannot have in-type B. Finally, if j − 1 ∈ J and sj ∈ S
then sj−1 cannot have
out-type B.
Let q+
:= |S+
| and define q−
and q−
similarly. Let Ȳ := V (D) \ Y = A ∪ B
and X := X ′ ∪X ′′ = Y \ S. Consider any pair a, b with a ∈ A and b ∈ B. Then
− 1 ≤ |N+(a)| ≤ q−
+ |N+
(a)|+ |N+
− 1 ≤ |N−(b)| ≤ q+
+ |N−
(b)|+ |N−
(b)|.
Since N+
(a)∩N−
(b) = ∅ (as D does not contain an A-B edge) and a, b /∈ N+
(b) we have
(a)|+ |N−
(b)| ≤ |Ȳ | − 2 = n− |X| − k − 2.
Adding (5) and (6) together now gives
− 2 ≤ q−
+ |N+
(a)|+ |N−
(b)|+ n− |X| − k − 2.
Hence
(a)∩N−
(b)| ≥ |N+
(a)|+|N−
(b)|−|X| ≥ 2
−n+k−q−
≥ 2k−q−
Similarly, using Claim 4, one can show that
(8) |N−
(a) ∩N+
(b)| ≥ 2k − q+
Consider any j ∈ J . Recall that by Claim 3 we have that either sj has out-
type A and sj+1 has in-type B or sj has out-type B and sj+1 has in-type A.
Let JAB denote the set of all those indices j ∈ J for which the former holds and
let JBA be the set of all those j ∈ J for which the latter holds. Our next aim is
to estimate jAB := |JAB | and jBA := |JBA|. Note that Claim 6 implies that if
sj ∈ S
then j /∈ JAB . As sk /∈ S
and k /∈ J , this shows that
jAB ≤ k − 1− |S
\ {sk}| = k − 1− |S
| = k − 1− q+
Also, if sj ∈ S
then j − 1 /∈ JAB by Claim 6. As s1 /∈ S
, this shows that
jAB ≤ k − 1− |S
\ {s1}| = k − 1− |S
| = k − 1− q−
Adding these two inequalites gives
(9) jAB ≤ k − 1−
In order to give an upper bound for jBA, note that if sj ∈ S
then j /∈ JBA by
Claim 6. Thus
jBA ≤ k − 1− |S
\ {sk}| ≤ k − q
10 DANIELA KÜHN AND DERYK OSTHUS
Also, if sj ∈ S
then j − 1 /∈ JBA by Claim 6. Thus
jBA ≤ k − 1− |S
\ {s1}| ≤ k − q
Adding these two inequalites gives
(10) jBA ≤ k −
Our next aim is to show that D contains a (S, J ∪{k})-system. This will complete
the proof of Theorem 2 since it contradicts the choice of our (S, J, T )-system.
Pick distinct vertices a0 ∈ A, aj ∈ N
(sj) for all j ∈ JAB , a
j ∈ N
(sj+1) for
all j ∈ JBA, b0 ∈ B, bj ∈ N
(sj+1) for all j ∈ JAB and b
j ∈ N
(sj) for all
j ∈ JBA. Choose a vertex x0 ∈ N
(a0) ∩ N
(b0) and link sk to s1 by the path
Qk := ska0x0b0s1. (This can be done since the right hand side of (7) is at least 2.)
To find the other paths, we distinguish two cases.
Case 1. jBA ≤ jAB
For all j ∈ JBA we pick a vertex xj ∈ N
(a′j) ∩N
(b′j) such that all these xj are
pairwise distinct and distinct from x0. Inequalities (8) and (10) together imply
that this can be done. Inequality (7) together with the fact that
2k − q−
− 1− jBA
≥ 2jAB + 1− jBA ≥ jAB + 1,
implies that for all j ∈ JAB we can now pick a vertex xj ∈ N
(aj) ∩ N
such that x0 and all the xj (j ∈ J) are pairwise distinct. If j ∈ JAB we link sj
to sj+1 by the path Qj := sjajxjbjsj+1. If j ∈ JBA we link sj to sj+1 by the path
Qj := sjb
jsj+1. The paths Qj (j ∈ J) and Qk are internally disjoint and have
length 4, so they form an (S, J ∪ {k})-system, as required.
Case 2. jBA > jAB
We proceed similiarly as in Case 1, but this time we choose the vertices xj ∈
(aj) ∩N
(bj) for all j ∈ JAB first. As
2k − q+
− 1− jAB
≥ 2jBA − 1− jAB > jBA − 1,
inequality (8) implies that we can then pick the vertices xj ∈ N
(a′j) ∩ N
(b′j)
for all j ∈ JBA. The paths Qj (j ∈ J) and Qk are then defined as before. This
completes the proof of Theorem 2.
Note that throughout the proof, the paths we constructed always had length at
most 6 (the only case where they had length exactly 6 was in the proof of Claim 4).
This means that the proof can easily be translated into polynomial algorithm so
that the exponent of the running time does not depend on k: We simply start with
any (S, J, T )-system with J ⊆ I. Now we go through the steps of the proof and
find a ‘better’ (S, J ′, T ′)-system with J ′ ⊆ I. Claim 1 implies that for fixed k we
only need to do this a bounded number of times. Since the paths we need have
length at most 6 and there are only a bounded number of cases to consider in
the proof, it is clear that one can find the better system in polynomial time with
exponent independent of k. Altogether this means that the problem of finding a
cycle encountering a given sequence of k vertices is fixed parameter tractable for
digraphs whose minimum degree satisfies the conditon in Theorem 2 (where k is
LINKEDNESS AND ORDERED CYCLES IN DIGRAPHS 11
the fixed parameter). The same applies to the problem of linking ℓ given pairs of
vertices. In general, even the problem of deciding whether a digraph is 2-linked
is already NP-complete [10]. For a survey on fixed parameter tractable digraph
problems, see [8].
5. Acknowledgement
We are grateful to Andrew Young for reading through the manuscript.
References
[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer,
2000.
[2] B. Bollobás and A. Thomason, Highly linked graphs, Combinatorica 16 (1996), 313–320.
[3] G. Chen, R.J. Faudree, R.J. Gould, L. Lesniak and M.S. Jacobson, Linear forests and ordered
cycles, Discussiones Mathematicae – Graph theory 24 (2004), 47–54.
[4] Y. Egawa, R. Faudree, E. Györi, Y. Ishigami, R. Schelp and H. Wang, Vertex-disjoint cycles
containing specified edges, Graphs and Combinatorics 16 (2000), 81–92.
[5] M. Ferrara, R. Gould, G. Tansey and T. Whalen, On H-linked graphs, Graphs and Combi-
natorics 22 (2006), 217–224.
[6] A. Ghouila-Houri, Une condition suffisante d’existence d’un circuit Hamiltonien, C. R. Acad.
Sci. Paris 251 (1960), 495–497.
[7] R. Gould, A.V. Kostochka and G. Yu, On minimum degree implying that a graph is H-linked,
SIAM J. on Discrete Math., to appear.
[8] G. Gutin and A. Yeo, Some parameterized problems on digraphs, preprint 2007.
[9] M.C. Heydemann and D. Sotteau, About some cyclic properties in digraphs, J. Combinatorial
Theory B 38 (1985), 261–278.
[10] S. Fortune, J.E. Hopcroft, J. Wyllie, The directed subgraph homeomorphism problem, The-
oretical Computer Science 10 (1980), 111–121.
[11] H.A. Jung, Eine Verallgemeinerung des k-fachen Zusammenhangs für Graphen, Math. An-
nalen 187 (1970), 95–103.
[12] K. Kawarabayashi, A. Kostochka and G. Yu, On sufficient degree conditions for a graph to
be k-linked, Combinatorics, Probability and Computing, to appear.
[13] H. Kierstead, G. Sarközy and S. Selkow, On k-ordered Hamiltonian graphs, J. Graph The-
ory 32 (1999), 17–25.
[14] A. Kostochka and G. Yu, An extremal problem for H-linked graphs, J. Graph Theory 50
(2005), 321–339.
[15] A. Kostochka and G. Yu, Minimum degree conditions for H-linked graphs, Discrete Applied
Math., to appear.
[16] Y. Manoussakis, k-linked and k-cyclic digraphs, J. Combinatorial Theory B 48 (1990), 216–
[17] R. Thomas and P. Wollan, An improved extremal function for graph linkages, European
Journal of Combinatorics 26 (2005), 309–324.
[18] C. Thomassen, Note on highly connected non-2-linked digraphs, Combinatorica 11 (1991),
393–395.
Daniela Kühn, Deryk Osthus
School of Mathematics
University of Birmingham
Edgbaston
Birmingham
B15 2TT
E-mail addresses: {kuehn,osthus}@maths.bham.ac.uk
	1. Introduction
	2. Further work and open problems
	3. Notation and extremal examples
	4. Proof of Theorem ??
	5. Acknowledgement
	References
