# Complementary Cycles in Irregular Multipartite Tournaments

Authors: Zhihong He; Xiaoying Wang; Caiming Zhang
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph. A digraphD is cycle complementary if there exist two vertex disjoint cycles C and C
′ such that V
(
D
)
=
V
(
C
)
∪
V
(
C
′
). Let D be a locally almost regular c-partite tournament with c
≥
3 and |
γ
(
D
)
|
≤
3 such that all partite sets have the same cardinality r, and let C
3 be a 3-cycle of D. In this paper, we prove that if D
-
V
(
C
3
) has no cycle factor, then D contains a pair of disjoint cycles of length 3 and |
V
(
D
)
|
-
3, unless D is isomorphic to T
7, D
4,2, D
4,2
⁎, or D
3,2.


---

## Body

## 1. Introduction

Denote the vertex set and arc set of a digraphD by V
(
D
) and E
(
D
), respectively. For a subset X of V
(
D
), we define D
[
X
] as the subdigraph induced by X. If x
y is an arc of a digraph D, then we write x
→
y and say x
dominates
y. If X and Y are two disjoint subsets of V
(
D
) or subdigraphs of D such that every vertex of X dominates every vertex of Y, then X
dominates
Y, denoted by X
→
Y. We write X
⇒
Y if there is no arc from Y to X.Theout-neighborhood
N
D
+
(
x
)
=
N
+
(
x
) of a vertex x is the set of vertices dominated by x, and thein-neighborhood
N
D
-
(
x
)
=
N
-
(
x
) is the set of vertices dominating x. The numbers d
D
+
(
x
)
=
d
+
(
x
)
=
|
N
+
(
x
)
| and d
D
-
(
x
)
=
d
-
(
x
)
=
|
N
-
(
x
)
| are theoutdegree andindegree of x, respectively. Theminimum outdegree and theminimum indegree of D are denoted by δ
+
(
D
)
=
δ
+ and δ
-
(
D
)
=
δ
- and δ
(
D
)
=
δ
=
min
⁡
{
δ
+
,
δ
-
}. Thelocal irregularity is defined by i
l
(
D
)
=
max
⁡
|
d
+
(
x
)
-
d
-
(
x
)
| over all vertices x of D and theglobal irregularity is defined by i
g
(
D
)
=
max
⁡
{
max
⁡
(
d
+
(
x
)
,
d
-
(
x
)
)
-
min
⁡
(
d
+
(
y
)
,
d
-
(
y
)
)
∣
x
,
y
∈
V
(
D
)
}. Clearly, i
l
(
D
)
≤
i
g
(
D
). If i
g
(
D
)
=
0, then D isregular and if i
g
(
D
)
≤
1, then D isalmost regular. If i
l
(
D
)
≤
1, then D islocally almost regular.By a path or cycle we mean a directed path or cycle. A cycle of lengthm is an m-cycle. Theindependence number
α
(
D
)
=
α is the maximum size among all independent sets of vertices of D. A digraph D isstrongly connected orstrong if, for each pair of vertices u and v, there is a path from u to v in D. A digraph D with at least k
+
1 vertices is k-connected if for any set A of at most k
-
1 vertices, the subdigraph D
-
A obtained by deleting A is strong. Theconnectivity of D, denoted by κ
(
D
), is defined to be the largest value of k such that D is k-connected.Acycle factor is a spanning subdigraph consisting of disjoint cycles. A cycle factor with the minimum number of cycles is called aminimal cycle factor. If we replace every arc x
y of D by y
x, then we call the resulting digraph, denoted by D
-
1, theconverse digraph of D.Ac-partite graph is a graph whose vertices are or can be partitioned into c different independent sets. Equivalently, it is a graph that can be colored with c colors, so that no two endpoints of an edge have the same color. A complete c-partite graph is a graph that can be partitioned into c independent sets, as above, so that every pair of vertices from two different independent sets have different colors.Ac-partite ormultipartite tournament is an orientation of a complete c-partite graph. If D is a c-partite tournament with the partite sets V
1
,
V
2
,
…
,
V
c such that |
V
1
|
≤
|
V
2
|
≤
⋯
≤
|
V
c
|, then we define γ
(
D
)
=
|
V
1
|. If the vertex x of D belongs to the partite set V
i, then we define V
(
x
)
=
V
i.A digraphD iscycle complementary if there exist two vertex disjoint cycles C and C
′ such that V
(
D
)
=
V
(
C
)
∪
V
(
C
′
). The problem of complementary cycles in tournaments was almost completely solved by Reid [1] in 1985 and by Song [2] in 1993. The authors proved that every 2-connected tournament D on at least 8 vertices has complementary cycles of length t and |
V
(
D
)
|
-
t for all t
∈
{
3,4
,
…
,
|
V
(
D
)
|
-
3
}.There exists only the following conjecture.Conjecture 1 (see Yeo [3] 1999).
A regularc-partite tournament D with c
≥
4 and |
V
(
D
)
|
≥
8 has a pair of vertex disjoint cycles of length t and |
V
(
D
)
|
-
t for all t
∈
{
3,4
,
…
,
|
V
(
D
)
|
-
3
}.In 2005, Volkmann [4] confirmed the first conjecture for t
=
3, unless D is a regular 4-partite tournament with two vertices in each partite set. In 2004, Volkmann [5] confirmed conjecture for t
=
4. In 2009, He et al. [6] confirmed conjecture for t
=
5. In 2013, Volkmann [7] confirmed every almost regularc-partite tournament D with |
V
(
D
)
|
≥
8 such that all partite sets have the same cardinality r. If c
≥
5 or c
=
4 and r
≥
6, thenD contains a pair of vertex disjoint directed cycles of lengths 4 and |
V
(
D
)
-
4
|. In 2014, Bai et al. [8] confirmed every regular bipartite tournament contains two complementary cycles. In 2014, He et al. [9] characterized all locally almost regular multipartite tournaments D whose partite sets have the same cardinality with γ
(
D
)
≥
4 that contain two complementary cycles of length 3 and |
V
(
D
)
|
-
3. Let D be a locally almost regular c-partite tournament with c
≥
3 and |
γ
(
D
)
|
≤
3 such that all partite sets have the same cardinality, and let C
3 be a 3-cycle of D. We prove if D
-
V
(
C
3
) has no cycle factor, then D contains a pair of disjoint cycles of length 3 and |
V
(
D
)
|
-
3, unless D is isomorphic to T
7, D
4,2, D
4,2
∗, or D
3,2.


## 2. Preliminary Results

The following results play important roles in the proof of our main theorem (Theorem12), where the first one is immediate.Lemma 2 (see [7]).
IfD is a regular c-partite tournament with the partite sets V
1
,
V
2
,
…
,
V
c, then α
(
D
)
=
|
V
1
|
=
|
V
2
|
=
⋯
=
|
V
c
|.Lemma 3 (see Yeo [10] 1998).
IfD is a multipartite tournament, then (1)
κ
D
≥
V
D
-
2
i
l
D
-
α
D
3
.Lemma 4 (see Reid [1] 1985 and Song [2] 1993).
IfD is a 2-connected tournament with at least 6 vertices, then D contains two complementary cycles of length t and |
V
(
D
)
|
-
t for all 3
≤
t
≤
|
V
(
D
)
|
/
2, unless it is isomorphic to the tournament T
7.Lemma 5 (see Bondy [11] 1976).
Each strongc-partite tournament with c
≥
3 contains an m-cycle for each m
∈
{
3,4
,
…
,
c
}.Lemma 6 (see Yeo [12] 1999).
LetD be a c-partite tournament with the partite sets V
1
,
V
2
,
…
,
V
c such that k
=
|
V
1
|
≤
|
V
2
|
≤
⋯
≤
|
V
c
|
=
k
+
i for some i
∈
{
0,1
}. If (2)
i
l
D
≤
V
D
-
V
c
-
1
-
2
V
c
+
2
2
,then D is Hamiltonian.Lemma 7 (see Volkmann [5] 2004).
LetD be a regular 3-partite tournament with |
V
(
D
)
|
≥
6. Then D contains two complementary cycles of length 3 and |
V
(
D
)
|
-
3, unless D is isomorphic to D
3,2.Lemma 8 (see Volkmann [4] 2005).
LetD be a regular c-partite tournament with c
≥
4 and |
V
(
D
)
|
≥
6. Then D contains two complementary cycles of length 3 and |
V
(
D
)
|
-
3, unless D is isomorphic to T
7, D
4,2, or D
4,2
∗.Lemma 9 (see Tewes [13] 2002).
IfD is a multipartite tournament, then (3)
δ
D
≥
V
D
-
i
l
D
-
α
D
2
≥
V
D
-
i
g
D
-
α
D
2
.Lemma 10 (see Yeo [12] 1999 and Gutin and Yeo [14] 2000).
A digraphD has no cycle factor if and only if its vertex set V
(
D
) can be partitioned into four subsets Y
,
Z
,
R
1, and R
2 such that(4)
R
1
⟹
Y
,
R
1
∪
Y
⟹
R
2
,
Y
>
Z
,where Y is an independent set.Lemma 11 (see Volkmann and Winzen [15] 2004).
LetV
1
,
V
2
,
…
,
V
c be the partite sets of a c-partite tournament D with no cycle factor such that |
V
1
|
≤
|
V
2
|
≤
⋯
≤
|
V
c
|. According to Lemma 10, the vertex set V
(
D
) can be partitioned into subsets Y
,
Z
,
R
1 and R
2 satisfying (4) such that |
Z
|
+
k
+
1
≤
|
Y
|
≤
|
V
c
|
-
t with integers k
,
t
≥
0. Let V
i be the partite set with the property that Y
⊆
V
i. If Q
=
V
(
D
)
-
Z
-
V
i, Q
1
=
Q
∩
R
1, and Q
2
=
Q
∩
R
2, then(5)
i
l
D
≥
V
D
-
3
V
c
+
2
t
+
2
k
+
2
,
i
g
D
≥
V
D
-
V
c
-
1
-
2
V
c
+
3
k
+
3
2
,if Q
1
=
∅ or Q
2
=
∅ case part (1) of lemma and(6)
i
g
D
≥
i
l
D
≥
V
D
-
V
c
-
1
-
2
V
c
+
3
k
+
3
+
t
2
, if Q
1
≠
∅ and Q
2
≠
∅ case part (2) of lemma.


## 3. Main Result

Theorem 12.
LetD be a locally almost regular c-partite tournament with c
≥
3 and |
γ
(
D
)
|
≤
3 such that all partite sets have the same cardinality, and let C
3 be a 3-cycle of D. We prove that if D
-
V
(
C
3
) has no cycle factor, then according to Lemma 10, the vertex set V
(
D
) can be partitioned into subsets Y
,
Z
,
R
1 and R
2 satisfying (4) such that R
1
⇒
Y
,
(
R
1
∪
Y
)
⇒
R
2 and |
Y
|
>
|
Z
|, where Y is an independent set. If |
Z
∪
Y
|
≤
4, then D contains a pair of disjoint cycles of length 3 and |
V
(
D
)
|
-
3, unless D is isomorphic to T
7, D
4,2, D
4,2
∗, or D
3,2.Proof.
First of all notice that the condition that all partite sets have the same cardinality shows thati
l
(
D
)
=
i
g
(
D
). Let V
1
,
V
2
,
…
,
V
c be the partite sets of a locally almost regular c-partite tournament D such that |
V
1
|
=
|
V
2
|
=
⋯
=
|
V
c
|
=
r. If |
V
(
D
)
|
-
r is even, then it is easy to say that D is regular. Thus, if c
=
3, then D is a regular 3-partite tournament, and by Lemma 7, D contains two complementary cycles of length 3 and |
V
(
D
)
|
-
3, unless D is isomorphic to D
3,2.
According to Lemma3, we have (7)
κ
D
≥
V
D
-
2
i
l
D
-
α
D
3
.
Ifc
≥
7 and r
=
1, which means that D is a tournament, then (7) yields κ
(
D
)
≥
2. In addition, if c
=
6 and r
=
1, then it can be shown that κ
(
D
)
≥
2 too. Hence Lemma 4 implies that D contains two complementary cycles of length 3 and |
V
(
D
)
|
-
3, unless D is isomorphic to T
7.
Therefore we only need to consider the casec
≥
4 and 2
≤
r
≤
3. In view of Lemma 3, κ
(
D
)
≥
2 and thus Lemma 5 ensures the existence of a 3-cycle C
3 in D. If we define in the case r
≥
2 the c-partite tournament H by H
=
D
-
V
(
C
3
), then i
l
(
H
)
≤
4, and |
V
(
H
)
|
=
c
r
-
3. If V
1
′
,
V
2
′
,
…
,
V
c
′ are the partite sets of H such that |
V
1
′
|
≤
|
V
2
′
|
≤
⋯
≤
|
V
c
′
|, then |
V
1
′
|
=
r
-
1 and |
V
c
′
|
=
r. With exception of the cases c
=
4 and r
=
2,3
,
c
=
5 and r
=
2,3, c
=
6 and r
=
2, and c
=
7 and r
=
2, this leads to (8)
i
l
H
≤
4
≤
V
H
-
V
c
-
1
′
-
2
V
c
′
+
2
2
. Applying Lemma 6, we conclude that H has a Hamiltonian cycle C, and we obtain the desired result that V
(
D
)
=
V
(
C
3
)
∪
V
(
C
). Since D is a regular c-partite tournament for c
=
4 and r
=
2, c
=
5 and r
=
2,3, c
=
6 and r
=
2, and c
=
7 and r
=
2, by Lemma 8, D contains two complementary cycles of length 3 and |
V
(
D
)
|
-
3, unless D is isomorphic to D
4,2, or D
4,2
∗. Therefore, there only remain the cases c
=
4 and r
=
3.
LetV
1
=
{
u
1
,
u
2
,
u
3
}, V
2
=
{
v
1
,
v
2
,
v
3
}, V
3
=
{
w
1
,
w
2
,
w
3
}, V
4
=
{
x
1
,
x
2
,
x
3
} be the partite sets of D, C
3
=
u
3
v
3
w
3
u
3, and H
=
D
-
V
(
C
3
). Then α
(
D
)
=
3 and 4
≤
d
D
+
(
x
)
,
d
D
-
(
x
)
≤
5 for each x
∈
V
(
D
). Then i
l
(
H
)
≤
4, and |
V
(
H
)
|
=
9. If V
1
′
,
V
2
′
,
V
3
′
,
V
4
′ are the partite sets of H such that |
V
1
′
|
≤
|
V
2
′
|
≤
|
V
3
′
|
≤
|
V
4
′
|, then |
V
1
′
|
=
|
V
2
′
|
=
|
V
3
′
|
=
2 and |
V
4
′
|
=
3. Then by Lemma 10, the vertex set V
(
H
) can be partitioned into subsets Y
,
Z
,
R
1, R
2 such that R
1
⇒
Y
,
(
R
1
∪
Y
)
⇒
R
2
,
|
Y
|
>
|
Z
|, and Y is an independent set. Let, without loss of generality, |
R
1
|
≤
|
R
2
| (if |
R
1
|
≥
|
R
2
|, then we consider D
-
1 ). By Lemma 9, δ
(
H
)
≥
1.
Case 1. Z
=
∅ and |
Y
|
=
1,2
,
3. Then R
1
≠
∅. Otherwise d
D
+
(
x
)
≥
6 and d
D
-
(
x
)
≤
3 for x
∈
Y which contradicts i
l
(
D
)
≤
1. Consider |
R
1
|
≠
1, 2 for δ
(
H
)
≥
1. So 3
≤
|
R
1
|
≤
4.
Assume that|
Y
|
=
1. We claim that |
R
1
|
≠
3, or else since d
H
+
(
x
)
,
d
H
-
(
x
)
≥
1
,
x
∈
V
(
H
), R
1 induces a 3-cycle, and thus there is a vertex y
∈
R
1 such that |
V
(
y
)
∩
(
Y
∪
R
2
)
|
≤
1. It follows that d
D
+
(
y
)
≥
6 and d
D
-
(
y
)
≤
3, a contradiction to i
l
(
D
)
≤
1. Assume that |
R
1
|
=
4. If R
1 is bipartite, then since δ
(
H
)
≥
1, each partite set of R
1 consists of two vertices. Hence, R
1 induces a 4-cycle and thus there is a vertex y
∈
R
1 such that |
V
(
y
)
∩
(
Y
∪
R
2
)
|
≤
1. It follows that d
D
+
(
y
)
≥
6 and d
D
-
(
y
)
≤
3, a contradiction to i
l
(
D
)
≤
1. If R
1 is 3-partite, then there exists a vertex y
∈
R
1 such that |
V
(
y
)
∩
(
Y
∪
R
2
)
|
≤
2 and d
R
1
+
(
y
)
≥
2 or |
V
(
y
)
∩
(
Y
∪
R
2
)
|
≤
1 and d
R
1
+
(
y
)
≥
1. This leads to d
D
+
(
y
)
≥
6 and d
D
-
(
y
)
≤
3, a contradiction to i
l
(
D
)
≤
1. If R
1 is 4-partite, then y
∈
R
1 such that |
V
(
y
)
∩
(
Y
∪
R
2
)
|
≤
1 and d
R
1
+
(
y
)
≥
2; then d
D
+
(
y
)
≥
6 and d
D
-
(
y
)
≤
3, a contradiction to i
l
(
D
)
≤
1.
If|
Y
|
=
2, then |
R
1
|
≤
3. Note that δ
(
H
)
≥
1, R
1 induces a 3-cycle. So there is a vertex y
∈
R
1 such that d
D
+
(
y
)
≥
6 and d
D
-
(
y
)
≤
3, a contradiction to i
l
(
D
)
≤
1.
If|
Y
|
=
3, then replacing k by 2 and t by 0 in Lemma 11 leads us to i
l
(
H
)
≥
5, a contradiction to i
l
(
H
)
≤
4.
Case 2. One has |
Z
|
=
1 and |
Y
|
=
2. We discuss this case by the value of |
R
1
|, where |
R
1
|
=
0,1
,
2,3
.
Case 2.1. Assume that |
R
1
|
=
0; that is, R
1
=
∅.
Note thatZ
→
Y since δ
(
H
)
≥
1. If Y
⊂
V
i, for some i
∈
{
1,2
,
3
}, then R
2
∩
V
i
=
∅. Then d
D
+
(
y
)
≥
6 and d
D
-
(
y
)
≤
3 for y
∈
Y, a contradiction. Therefore, Y
⊂
V
4. Assume, without loss of generality, that Y
=
{
x
1
,
x
2
}, x
3
∈
R
2, and Z
=
{
u
1
}. Since i
l
(
D
)
≤
1, V
(
C
3
)
→
Y, and there exists one vertex in {
v
1
,
v
2
,
w
1
,
w
2
}, say, v
1 such that v
1
→
u
1.
Case 2.1.1. Assume that H
[
{
u
2
,
v
2
,
w
1
,
w
2
,
x
3
}
] has a Hamiltonian path.
(1) Assume that there is a Hamiltonian path which does not end at x
3 or begin at x
3, say, p
1
p
2
p
3
p
4
p
5 with x
3
∉
{
p
1
,
p
5
} in H
[
{
u
2
,
v
2
,
w
1
,
w
2
,
x
3
}
]. If p
5 does not dominate p
1, then p
5 has at least one positive neighbor x in C
3, and there are the complementary cycles x
1
v
1
u
1
x
1 and x
2
p
1
p
2
p
3
p
4
p
5
x
x
+
x
+
+
x
2. If p
5
→
p
1, then there exist at least two arcs from {
p
1
,
p
2
,
p
3
,
p
4
,
p
5
} to C
3. Let, without loss of generality, p
i
→
x with p
i
+
≠
x
3 and x
∈
V
(
C
3
). This leads to the complementary cycles x
1
v
1
u
1
x
1 and x
2
p
i
+
1
p
i
+
2
⋯
p
i
x
x
+
x
+
+
x
2, all indices are taken modulo 5.
(2) If there is a Hamiltonian path ending at x
3 in H
[
{
u
2
,
v
2
,
w
1
,
w
2
,
x
3
}
], say, p
1
p
2
p
3
p
4
p
5 with p
5
=
x
3, then we need only to consider {
p
1
,
p
2
,
p
3
}
→
p
5. The other cases are easily reduced to (1). Thus p
5 has at least one positive neighbor in C
3, say, x. This leads to the complementary cycles x
1
v
1
u
1
x
1 and x
2
p
1
p
2
p
3
p
4
p
5
x
x
+
x
+
+
x
2.
(3) If there is a Hamiltonian path beginning at x
3 in H
[
{
u
2
,
v
2
,
w
1
,
w
2
,
x
3
}
], say, p
1
p
2
p
3
p
4
p
5 with p
1
=
x
3, then we need only to consider p
1
→
{
p
2
,
p
3
,
p
4
,
p
5
}. The other cases are easily reduced to (1) or (2).
Assume thatp
1
→
v
1. Then (
V
(
C
3
)
∪
{
u
1
}
)
→
p
1, and we obtain a 3-cycle p
1
v
1
u
1
p
1. Next we are to find its complementary cycle. Since i
l
(
D
)
≤
1, p
5 dominates at least one vertex x of C
3, and there exists at least one vertex of {
p
2
,
p
3
,
p
4
}, say, p
i, such that p
i
→
y with i
∈
{
2,3
,
4
}, y
∈
V
(
C
3
) and x
≠
y. This leads to the complementary cycles C
1
=
p
1
v
1
u
1
p
1 and C
2
=
x
1
p
2
⋯
p
i
y
y
+
x
2
p
i
+
1
⋯
p
5
x
x
1 if y
=
x
+ or C
2
=
x
1
p
2
⋯
p
i
y
x
2
p
i
+
1
⋯
p
5
x
x
+
x
1 if y
=
x
-.
Now assume thatv
1
→
p
1. If there is a vertex p
i of {
p
2
,
p
3
,
p
4
,
p
5
} that dominates u
1
(
i
∈
{
2,3
,
4,5
}
), then let p
i take the place of v
1, the above case being reduced to (1) of Case 2.1
.
1. Therefore, we let u
1
⇒
{
p
2
,
p
3
,
p
4
,
p
5
}. Then we have p
1
∪
V
(
C
3
)
⇒
u
1.
Ifu
2
∉
{
p
3
,
p
5
} and V
(
p
3
)
≠
V
(
p
5
), then there exists an arc between p
3 and p
5. Let, without loss of generality, p
3
→
p
5. This leads to the contradiction d
D
-
(
p
5
)
≥
6.
Ifu
2
∉
{
p
3
,
p
5
} and V
(
p
3
)
=
V
(
p
5
), then {
p
3
,
p
5
}
=
{
w
1
,
w
3
} and {
p
3
,
p
5
}
⇒
{
v
1
}
∪
V
(
C
3
) and p
5
→
p
2. If p
2
→
p
4, then p
4
=
u
2, p
2
=
v
2, {
p
2
,
p
4
}
⇒
{
v
1
}
∪
V
(
C
3
), and v
1
⇒
V
(
C
3
). This leads to the complementary cycles p
2
p
4
p
5
p
2 and x
1
p
3
u
3
x
2
v
1
p
1
v
3
w
3
u
1
x
1. If p
4
→
p
2, then p
2
=
u
2, p
4
=
v
2, {
p
2
,
p
4
}
⇒
{
v
1
}
∪
V
(
C
3
), and v
1
⇒
V
(
C
3
). This leads to the complementary cycles p
2
p
3
p
4
p
2 and x
1
p
5
u
3
x
2
v
1
p
1
v
3
w
3
u
1
x
1.
Ifu
2
∈
{
p
3
,
p
5
}, let, without loss of generality, p
5
=
u
2; then we have V
(
p
2
)
=
V
(
p
4
)
=
V
(
w
1
), p
3
=
v
2, p
3
→
p
5, p
5
→
p
2, {
p
2
,
p
4
,
p
5
}
→
v
1, and {
v
1
,
p
2
,
p
3
,
p
4
,
p
5
}
⇒
V
(
C
3
). This leads to the complementary cycles p
2
p
3
p
5
p
2 and x
1
v
1
p
1
u
1
x
2
p
4
u
3
v
3
w
3
x
1.
Case 2.1.2. Now we assume that H
[
{
u
2
,
v
2
,
w
1
,
w
2
,
x
3
}
] has no Hamiltonian path. Then let, without loss of generality, u
2
→
v
2.
(1)Assume that v
2 dominates one vertex {
w
1
,
w
2
}, say, v
2
→
w
2.
(a) Ifw
2
→
x
3, then since H
[
{
u
2
,
v
2
,
w
1
,
w
2
,
x
3
}
] has no Hamiltonian path, w
1
→
x
3, {
u
2
,
v
2
}
→
{
w
1
,
x
3
}, and u
2
→
w
2.
If there is one vertex of{
w
1
,
w
2
} that dominates u
1, let, without loss of generality, w
1
→
u
1; then let w
1 take the place of v
1, the case being reduced to (1) of Case 2.1
.
1. Therefore, let u
1
→
{
w
1
,
w
2
}. Then we have {
w
1
,
w
2
}
⇒
(
{
v
1
}
∪
V
(
C
3
)
). Since i
l
(
D
)
≤
1, x
3
→
u
3 or x
3
→
v
3. In the former case there are complementary cycles w
1
v
1
u
1
w
1 and x
1
u
2
x
3
u
3
x
2
v
2
w
2
v
3
w
3
x
1; in the latter case complementary cycles are w
1
v
1
u
1
w
1 and x
1
u
2
w
2
u
3
x
2
v
2
x
3
v
3
w
3
x
1.
(b) Assume thatx
3
→
w
2.
Ifw
1
→
u
2, then since H
[
{
u
2
,
v
2
,
w
1
,
w
2
,
x
3
}
] has no Hamiltonian path, {
w
1
,
u
2
,
v
2
}
→
x
3. This leads to the Hamiltonian path w
1
u
2
v
2
x
3
w
2, a contradiction.
Ifu
2
→
w
1 and w
1
→
v
2, then since H
[
{
u
2
,
v
2
,
w
1
,
w
2
,
x
3
}
] has no Hamiltonian path, x
3
→
{
w
1
,
u
2
,
v
2
}. This leads to the Hamiltonian path x
3
u
2
w
1
v
2
w
2, a contradiction.
Ifu
2
→
w
1 and v
2
→
w
1, then since H
[
{
u
2
,
v
2
,
w
1
,
w
2
,
x
3
}
] has no Hamiltonian path, x
3
→
w
1, u
2
→
w
2, and {
w
1
,
w
2
}
⇒
(
{
v
1
,
u
1
}
∪
V
(
C
3
)
). If v
2
→
x
3 or x
3
→
v
2 and u
2
→
x
3, then let w
1 take the place of v
1, the case being reduced to (1) of Case 2.1
.
1. If x
3
→
v
2 and x
3
→
u
2, then let w
1 take the place of v
1, the case being reduced to (3) of Case 2.1
.
1.
(2) Assume that {
w
1
,
w
2
}
→
v
2. Then we have v
2
⇒
(
Z
∪
V
(
C
3
)
∪
{
x
3
}
).
(a) Ifu
2 dominates one vertex of {
w
1
,
w
2
}, say, w
1, then since H
[
{
u
2
,
v
2
,
w
1
,
w
2, x
3
}
] has no Hamiltonian path, {
w
1
,
w
2
}
→
x
3 and u
2
→
{
x
3
,
w
2
}.
(i) Ifx
3
→
v
1 and v
1 dominates one vertex of {
w
1
,
w
2
}, then let v
2 take the place of v
1, the case being reduced to (3) of Case 2.1
.
1.
(ii) Ifx
3
→
v
1 and {
w
1
,
w
2
}
→
v
1, then let v
2 take the place of v
1, the case being reduced to (2) of Case 2.1
.
1.
(iii) Assume thatv
1
→
x
3; then we have x
3
→
(
Z
∪
V
(
C
3
)
).
Ifv
3 dominates one vertex of {
u
2
,
w
1
,
w
2
}, say, v
3
→
w
1, then we obtain the complementary cycles w
1
x
3
v
3
w
1 and x
1
v
1
u
1
x
2
u
2
w
2
v
2
w
3
u
3
x
1.
If{
u
2
,
w
1
,
w
2
}
→
v
3, then we have v
1
⇒
(
{
u
2
}
∪
V
(
C
3
)
). Then let v
2 take the place of v
1, the case being reduced to (2) of Case 2.1
.
1.
(b) Assume that{
w
1
,
w
2
}
→
u
2. Since H
[
{
u
2
,
v
2
,
w
1
,
w
2
,
x
3
}
] has no Hamiltonian path, {
w
1
,
w
2
}
→
x
3.
(i) Assume thatx
3
→
u
2. Then u
2
⇒
(
V
(
C
3
)
∪
{
v
1
}
).
Ifx
3
→
v
1, then v
1 dominates at least one vertex of {
w
1
,
w
2
}; then let v
2 take the place of v
1, the case being reduced to (1) of Case 2.1
.
1.
Ifv
1
→
x
3 and there exists one vertex of {
w
1
,
w
2
} that dominates at least one vertex of C
3, say, w
1
→
v
3, then we obtain the complementary cycles C
1
=
x
3
u
2
v
1
x
3 and C
2
=
x
1
w
2
v
2
u
1
x
2
w
1
v
3
w
3
u
3
x
1.
Ifv
1
→
x
3 and V
(
C
3
)
⇒
{
w
1
,
w
2
}, then R
2
∖
{
w
1
,
w
2
}
⇒
{
u
3
,
v
3
}. This leads to the complementary cycles C
1
=
w
1
v
2
u
3
w
1 and C
2
=
x
1
v
1
u
1
x
2
w
2
x
3
u
2
v
3
w
3
x
1.
(ii) Assume thatu
2
→
x
3.
Ifx
3
→
v
1 and v
1 dominates one vertex of {
w
1
,
w
2
}, then let v
2 take the place of v
1, the case being reduced to (1) of Case 2.1
.
1.
Assume that{
w
1
,
w
2
,
x
3
}
→
v
1. Then we have v
1
⇒
(
V
(
C
3
)
∪
{
u
2
}
) and u
2
⇒
V
(
C
3
). If there exists one vertex of {
w
1
,
w
2
} that dominates u
1, say, w
1
→
u
1, then let w
1 take the place of v
1, the case being reduced to (2) of Case 2.1
.
1. Therefore, let u
1
→
{
w
1
,
w
2
}. This leads to the complementary cycles C
1
=
w
1
v
1
u
1
w
1 and C
2
=
x
1
v
2
u
3
x
2
w
2
u
2
x
3
v
3
w
3
x
1.
Now assume thatv
1
→
x
3. Then we have x
3
→
(
{
u
1
}
∪
V
(
C
3
)
).
Letv
1 dominate one vertex of {
w
1
,
w
2
}, say, v
1
→
w
1.
Ifw
2
→
u
1, then we have the complementary cycles C
1
=
x
1
w
2
u
1
x
1 and C
2
=
x
2
v
1
w
1
u
2
v
2
x
3
u
3
v
3
w
3
x
2.
Ifu
1
→
w
2, then since i
l
(
D
)
≤
1, u
2 dominates at least one vertex of C
3. This leads to the complementary cycles C
1
=
w
2
v
2
u
1
w
2 and C
2
=
x
1
w
1
u
2
v
3
w
3
x
2
v
1
x
3
u
3
x
1 if u
2
→
v
3 or C
2
=
x
1
w
1
u
2
w
3
x
2
v
1
x
3
u
3
v
3
x
1 if u
2
→
w
3.
Now let{
w
1
,
w
2
}
→
v
1.
Ifu
1 dominates one vertex of {
w
1
,
w
2
}, say, u
1
→
w
1, then we obtain the complementary cycles C
1
=
v
1
u
1
w
1
v
1 and C
2
=
x
1
w
2
v
2
u
3
x
2
u
2
x
3
v
3
w
3
x
1.
If{
w
1
,
w
2
}
→
u
1, then we have u
1
⇒
V
(
C
3
) and V
(
C
3
)
⇒
{
w
1
,
w
2
}. This leads to the complementary cycles C
1
=
w
1
u
1
v
3
w
1 and C
2
=
x
1
w
2
u
2
v
2
w
3
x
2
v
1
x
3
u
3
x
1.
Case 2.2. Assume that |
R
1
|
=
1. If R
1
∩
V
4
=
∅, then |
V
(
x
)
∩
(
Y
∪
R
2
)
|
=
1 for x
∈
R
1. Therefore, we have d
D
+
(
x
)
≥
6 and d
D
-
(
x
)
≤
3 for x
∈
R
1, a contradiction. Hence, let, without loss of generality, R
1
=
{
x
3
}. If Y
=
{
x
1
,
x
2
}, then the case is equivalent to the case of “|
Y
|
=
2, x
3
∈
R
2, and x
3
→
R
2
∖
{
x
3
},” which has been proved in (3) of Case 2.1
.
1 and Case 2.1
.
2. If Z
∩
V
4
≠
∅, then d
D
+
(
x
3
)
≥
6, a contradiction. So, let, without loss of generality, Y
=
{
u
1
,
u
2
} and Z
=
{
v
1
}. Then (
V
(
C
3
)
∪
Z
)
⇒
R
1 and (
V
(
C
3
)
∪
Z
)
⇒
Y.
(1) Assume that there is an arc from {
x
1
,
x
2
} to v
1, say, x
1
→
v
1. Then we have C
1
=
x
1
v
1
u
1
x
1.
(a) Assume thatH
[
{
w
1
,
w
2
,
v
2
,
x
2
}
] has a Hamiltonian path.
If there is a Hamiltonian path which does not end atx
2 or begin at x
2, let, without loss of generality, p
1
p
2
p
3
p
4 with x
2
∉
{
p
1
,
p
4
} be a Hamiltonian path in H
[
{
w
1
,
w
2
,
v
2
,
x
2
}
]; then p
4 has at least one positive neighbor in C
3, say, p
4
→
u
3, and we have the complementary cycle C
2
=
w
3
x
3
u
2
p
1
p
2
p
3
p
4
u
3
v
3
w
3.
If there is a Hamiltonian path ending atx
2, let, without loss of generality, p
1
p
2
p
3
p
4 with p
4
=
x
2 be a Hamiltonian path in H
[
{
w
1
,
w
2
,
v
2
,
x
2
}
]; then we need only to consider {
p
1
,
p
2
,
p
3
}
→
p
4. The other cases are easily reduced to the above case which does not end at x
2. Thus p
4
→
(
{
v
1
}
∪
V
(
C
3
)
) and there is the complementary cycle C
2
=
u
3
x
3
u
2
p
1
p
2
p
3
p
4
v
3
w
3
u
3.
If there is a Hamiltonian path beginning atx
2, let, without loss of generality, p
1
p
2
p
3
p
4 with p
1
=
x
2 be a Hamiltonian path in H
[
{
w
1
,
w
2
,
v
2
,
x
2
}
]; then we need only to consider p
1
→
{
p
2
,
p
3
,
p
4
}. The other cases are easily reduced to the above case which does not begin at x
2. Thus p
4
⇒
(
{
v
1
,
x
1
}
∪
V
(
C
3
)
) and we have the complementary cycle C
2
=
x
3
u
2
p
1
p
2
p
3
p
4
u
3
v
3
w
3
x
3.
(b) Now we assume thatH
[
{
w
1
,
w
2
,
v
2
,
x
2
}
] has no Hamiltonian path. Let, without loss of generality, v
2
→
w
2.
Ifw
2
→
x
2, then since H
[
{
w
1
,
w
2
,
v
2
,
x
2
}
] has no Hamiltonian path, w
1
→
x
2, v
2
→
x
2, and v
2
→
w
1. Then we have x
2
→
V
(
C
3
) and w
1 dominates at least one vertex of C
3, say, w
1
→
u
3. This leads to the complementary cycle C
2
=
u
3
x
3
v
2
w
2
x
2
v
3
w
3
u
2
w
1
u
3.
Ifx
2
→
w
2 and v
2
→
x
2, then v
2
→
w
1 and x
2
→
w
1. This leads to {
w
1
,
w
2
}
⇒
V
(
C
3
) and the complementary cycle C
2
=
u
3
x
3
v
2
x
2
w
2
v
3
w
3
u
2
w
1
u
3.
Ifx
2
→
w
2 and x
2
→
v
2, then {
x
2
,
v
2
}
→
w
1 and {
w
1
,
w
2
}
⇒
V
(
C
3
). This leads to the complementary cycle C
2
=
u
3
x
3
v
2
w
1
v
3
w
3
u
2
x
2
w
2
u
3.
(2) Assume that v
1
→
{
x
1
,
x
2
}. Then we have (
{
w
1
,
w
2
}
∪
V
(
C
3
)
)
⇒
v
1, R
2
⇒
w
3, and C
1
=
w
1
v
1
u
1
w
1.
(a) Assume thatH
[
{
v
2
,
w
2
,
x
1
,
x
2
}
] has a Hamiltonian path. Then, since d
D
+
(
x
)
≤
5, there exists a Hamiltonian ending at x
1 or x
2; let, without loss of generality, p
1
p
2
p
3
p
4 with p
4
=
x
1 be a Hamiltonian path H
[
{
v
2
,
w
2
,
x
1
,
x
2
}
]. This leads to the complementary cycle C
2
=
w
3
u
3
v
3
x
3
u
2
p
1
p
2
p
3
p
4
w
3.
(b) Assume thatH
[
{
v
2
,
w
2
,
x
1
,
x
2
}
] has no Hamiltonian path.
Ifv
2
→
w
2, then w
2
→
x
1 or w
2
→
x
2, say, w
2
→
x
1. Since H
[
{
v
2
,
w
2
,
x
1
,
x
2
}
] has no Hamiltonian path, {
v
2
,
w
2
}
→
x
2 and v
2
→
x
1. This leads to {
x
1
,
x
2
}
→
V
(
C
3
) and we obtain the complementary cycle C
2
=
u
3
x
3
v
2
w
2
x
1
v
3
w
3
u
2
x
2
u
3.
Ifw
2
→
v
2, then v
2
→
x
1 or v
2
→
x
2, say, v
2
→
x
1. Since H
[
{
v
2
,
w
2
,
x
1
,
x
2
}
] has no Hamiltonian path, {
v
2
,
w
2
}
→
x
2 and w
2
→
x
1. This leads to {
x
1
,
x
2
}
→
V
(
C
3
) and we obtain the complementary cycle C
2
=
u
3
x
3
w
2
v
2
x
1
v
3
w
3
u
2
x
2
u
3.
Case 2.3. Assume that |
R
1
|
=
2. If R
1
∩
V
4
=
∅, then there exists a vertex x
∈
R
1 such that |
V
(
x
)
∩
R
1
|
=
2 or d
R
1
+
(
x
)
=
1. Each case leads to d
D
+
(
x
)
≥
6 and d
D
-
(
x
)
≤
3, a contradiction to i
l
(
D
)
≤
1. Therefore, R
1
∩
V
4
≠
∅. Let, without loss of generality, x
1
∈
R
1.
(1) Assume that R
1
⊂
V
4. Let, without loss of generality, R
1
=
{
x
1
,
x
2
} and Y
=
{
u
1
,
u
2
}. Then x
3
∈
R
2. Let, without loss of generality, Z
=
{
v
1
}. Since i
l
(
D
)
≤
1, (
Z
∪
V
(
C
3
)
)
⇒
R
1, v
2
→
w
1, or v
2
→
w
2, say, v
2
→
w
2. Then we have w
2
⇒
(
{
v
1
,
x
3
}
∪
V
(
C
3
)
)
.
Assume that there is an arc fromZ to Y, say, v
1
→
u
1.
Ifw
1
→
v
2, then we have v
2
⇒
(
V
(
C
3
)
∪
{
x
3
}
) and x
3 dominates at least two vertices of C
3. This leads to the complementary cycles C
1
=
u
1
w
2
v
1
u
1 and C
2
=
u
2
x
3
u
3
v
3
x
1
w
1
v
2
w
3
x
2
u
2 if x
3
→
u
3, or C
2
=
u
2
x
3
v
3
x
1
w
1
v
2
w
3
u
3
x
2
u
2 if x
3
→
v
3.
Ifv
2
→
w
1, then w
1
⇒
(
V
(
C
3
)
∪
{
x
3
}
), and x
3 dominates at least two vertices of C
3. This leads to the complementary cycles C
1
=
u
1
w
2
v
1
u
1 and C
2
=
u
2
x
3
u
3
x
1
v
2
w
1
v
3
w
3
x
2
u
2 if x
3
→
u
3, or C
2
=
u
2
x
3
v
3
x
1
v
2
w
1
w
3
u
3
x
2
u
2 if x
3
→
v
3.
Now assume thatY
→
Z. Then we have V
(
C
3
)
→
Y, R
2
⇒
w
3, and C
1
=
u
1
v
1
x
1
u
1.
Ifw
1
→
v
2, then we have v
2
⇒
(
V
(
C
3
)
∪
{
w
2
,
x
3
}
) and w
2
→
x
3. This leads to the complementary cycle C
2
=
u
2
w
1
v
2
w
2
x
3
w
3
u
3
v
3
u
2.
Ifv
2
→
w
1, then w
1
⇒
(
V
(
C
3
)
∪
{
x
3
}
) and we obtain the complementary cycle C
2
=
u
2
v
2
w
1
x
3
w
3
u
3
x
2
w
2
v
3
u
2.
(2) Assume that |
R
1
∩
V
4
|
=
1. Let, without loss of generality, R
1
=
{
x
1
,
u
1
}. Then x
1
→
u
1, u
2
∈
R
2, and (
Z
∪
V
(
C
3
)
)
⇒
R
1. Since i
l
(
D
)
≤
1, Z
∩
V
4
=
∅. Let, without loss of generality, Z
=
{
v
1
}.
(a) Assume thatY
∩
V
4
=
∅. Let, without loss of generality, Y
=
{
w
1
,
w
2
}. Then R
2
=
{
x
2
,
x
3
,
u
2
,
v
2
}.
(i) Assume that there is an arc fromY to Z, say, w
1
→
v
1. Then we have C
1
=
w
1
v
1
x
1
w
1.
IfH
[
R
2
] has a Hamiltonian path, then it ends at x
2 (or x
3). Let, without loss of generality, p
1
p
2
p
3
p
4 with p
4
∈
{
x
2
,
x
3
} be a Hamiltonian path in H
[
R
2
]. Then p
4 dominates at least two vertices of C
3. This leads to the complementary cycle C
2
=
w
2
p
1
p
2
p
3
p
4
u
3
v
3
w
3
u
1
w
2 if p
4
→
u
3 or C
2
=
w
2
p
1
p
2
p
3
p
4
w
3
u
3
v
3
u
1
w
2 if p
4
→
w
3.
Now assume thatH
[
R
2
] has no Hamiltonian path.
Ifu
2
→
v
2, then v
2
⇒
(
{
x
2
,
x
3
}
∪
V
(
C
3
)
). Since H
[
R
2
] has no Hamiltonian path, u
2
→
{
x
2
,
x
3
}. Then we have {
x
2
,
x
3
}
→
(
Z
∪
V
(
C
3
)
). If u
3
→
w
2, then we have the complementary cycle C
2
=
u
2
v
2
x
2
v
3
u
1
x
3
w
3
u
3
w
2
u
2. If w
2
→
u
3, then v
3
→
w
2 and we have the complementary cycle C
2
=
u
2
v
2
x
2
w
3
u
1
x
3
u
3
v
3
w
2
u
2.
Ifv
2
→
u
2, then u
2 dominates one vertex of {
x
2
,
x
3
}, say, u
2
→
x
2. Since H
[
R
2
] has no Hamiltonian path, v
2
→
{
x
2
,
x
3
} and u
2
→
x
3. Then we have {
x
2
,
x
3
}
→
(
Z
∪
V
(
C
3
)
). If u
3
→
w
2, then we have the complementary cycle C
2
=
v
2
u
2
x
2
v
3
u
1
x
3
w
3
u
3
w
2
v
2. If w
2
→
u
3, then v
3
→
w
2 and we have the complementary cycle C
2
=
v
2
u
2
x
2
w
3
u
1
x
3
u
3
v
3
w
2
v
2.
(ii) Assume thatZ
→
Y. Then there is an arc from {
x
2
,
x
3
} to Z, say, x
2
→
v
1. This leads to the 3-cycle C
1
=
w
1
x
2
v
1
w
1.
Ifu
2
→
v
2, then v
2
⇒
x
3 and x
3 dominates at least two vertices of C
3. This leads to the complementary cycle C
2
=
u
2
v
2
x
3
u
3
v
3
w
3
x
1
u
1
w
2
u
2 if x
3
→
u
3 or C
2
=
u
2
v
2
x
3
v
3
w
3
u
3
x
1
u
1
w
2
u
2 if x
3
→
v
3.
Ifv
2
→
u
2 and u
2
→
x
3, then x
3 dominates at least two vertices of C
3. This leads to the complementary cycle C
2
=
v
2
u
2
x
3
u
3
v
3
w
3
x
1
u
1
w
2
v
2 if x
3
→
u
3 or C
2
=
v
2
u
2
x
3
v
3
w
3
u
3
x
1
u
1
w
2
v
2 if x
3
→
v
3.
Ifv
2
→
u
2 and x
3
→
u
2, then u
2
⇒
V
(
C
3
). This leads to the complementary cycle C
2
=
v
2
x
3
u
2
v
3
w
3
u
3
x
1
u
1
w
2
v
2 if v
2
→
x
3 or C
2
=
x
3
v
2
u
2
v
3
w
3
u
3
x
1
u
1
w
2
v
2 if x
3
→
v
2.
(b) Assume thatY
⊂
V
4. Then let, without loss of generality, Y
=
{
x
2
,
x
3
}. Then we have R
2
=
{
u
2
,
v
2
,
w
1
,
w
2
}.
(i) Assume that there is an arc fromZ to Y, say, v
1
→
x
2. Then there is an arc from R
2 to Z.
If there is an arc from{
w
1
,
w
2
} to Z, say, w
1
→
v
1, then we have C
1
=
x
2
w
1
v
1
x
2. Let, without loss of generality, v
2
→
w
2. Then w
2
⇒
(
{
u
2
}
∪
V
(
C
3
)
) and u
2 dominates at least one vertex of C
3. This leads to the complementary cycle C
2
=
v
2
w
2
u
2
v
3
w
3
u
3
x
1
u
1
x
3
v
2 if u
2
→
v
3 or C
2
=
v
2
w
2
u
2
w
3
u
3
v
3
x
1
u
1
x
3
v
2 if u
2
→
w
3.
Otherwise,u
2
→
v
1. Then we have 3-cycle C
1
=
x
2
u
2
v
1
x
2. Let, without loss of generality, v
2
→
w
2. Then w
2
⇒
(
Z
∪
V
(
C
3
)
).
Ifw
1
→
v
2, then we have the complementary cycle C
2
=
x
3
w
1
v
2
w
2
u
3
v
3
w
3
x
1
u
1
x
3.
Ifv
2
→
w
1, then w
1
⇒
Z
∪
V
(
C
3
) and we have the complementary cycle C
2
=
v
2
w
2
u
3
x
1
w
1
v
3
w
3
u
1
x
3
v
2.
(ii) Assume thatY
→
Z. Then V
(
C
3
)
→
Y and we have 3-cycle C
1
=
x
2
v
1
u
1
x
2.
Ifw
2
→
v
2, then v
2
⇒
{
w
1
,
u
2
}
∪
V
(
C
3
), w
1
⇒
{
u
2
}
∪
V
(
C
3
), and u
2
⇒
V
(
C
3
). This leads to the complementary cycle C
2
=
w
2
v
2
u
3
x
1
w
1
u
2
v
3
w
3
x
3
w
2.
Now assume thatv
2
→
w
2. Then w
2
⇒
{
u
2
}
∪
V
(
C
3
).
Ifu
2
→
w
1, then w
1
⇒
V
(
C
3
) and we have the complementary cycle C
2
=
u
2
w
1
v
3
w
3
x
1
v
2
w
2
u
3
x
3
u
2.
Ifw
1
→
u
2, then u
2
⇒
V
(
C
3
) and we have the complementary cycle C
2
=
w
1
u
2
v
3
w
3
x
1
v
2
w
2
u
3
x
3
w
1.
Case 2.4. Assume that |
R
1
|
=
3.
LetR
1
∩
V
4
=
∅. If R
2
∩
V
4
≠
∅, then there exists one vertex x
∈
R
1 such that d
D
+
(
x
)
≥
6, a contradiction to i
l
(
D
)
≤
1. Therefore, Z
∪
Y
=
{
x
1
,
x
2
,
x
3
}. Let, without loss of generality, Z
=
{
x
1
}, Y
=
{
x
2
,
x
3
}. Since i
l
(
D
)
≤
1, let, without loss of generality, the set R
1 induce the 3-cycle u
1
v
1
w
1
u
1, and the set R
2 induces the 3-cycle u
2
v
2
w
2
u
2 such that R
2
⇒
Z
⇒
R
1. In addition, i
l
(
D
)
≤
1 implies R
2
⇒
V
(
C
3
)
⇒
R
1. It is evident that u
2
x
1
v
1
u
2 and x
2
v
2
u
3
w
1
x
3
w
2
v
3
w
3
u
1
x
2 are complementary cycles in D.
IfR
1
=
V
4, then there exist two vertices x
,
y
∈
R
2 such that (
V
(
x
)
∪
V
(
y
)
)
∩
(
Y
∪
R
1
)
=
∅. Since there is an arc between x and y, d
D
+
(
x
)
≥
6 or d
D
+
(
y
)
≥
6, a contradiction.
Therefore,R
1
∩
V
4
=
∅ and R
1
=
V
4. Thus |
R
1
∩
V
4
|
=
1 or 2.
(1) Assume that |
R
1
∩
V
4
|
=
1 first. Let, without loss of generality, {
x
1
,
u
1
}
⊂
R
1.
(a) Ifu
2
∈
R
1, then x
1
→
{
u
1
,
u
2
} and {
x
2
,
x
3
}
⊂
(
Y
∪
R
2
).
(i) IfY
=
{
x
2
,
x
3
}, then there exists one vertex x
∈
R
2 such that d
D
-
(
x
)
≥
6, a contradiction.
(ii) If, without loss of generality,Y
=
{
w
1
,
w
2
} and Z
=
{
v
1
}, then R
2
=
{
x
2
,
x
3
,
v
2
}. Then we have v
2
→
{
x
2
,
x
3
}, R
2
⇒
(
V
(
C
3
)
∪
Z
), and (
V
(
C
3
)
∪
Z
)
⇒
R
1. This leads to the complementary cycles C
1
=
x
2
v
2
u
1
x
2 and C
2
=
w
1
x
3
u
3
v
3
u
2
w
2
v
2
w
3
x
1
w
1.
(b) If, without loss of generality,v
1
∈
R
1 and we let u
1
→
v
1, then x
1
→
u
1, C
3
⇒
u
1, and u
2
∈
R
2.
(i) Letx
1
→
v
1.
Assume that{
x
2
,
x
3
}
⊂
R
2. Then Y
=
{
w
1
,
w
2
} and Z
=
{
v
2
}. In addition, i
l
(
D
)
≤
1 implies (
V
(
C
3
)
∪
Z
)
⇒
R
1.
Ifx
2
→
u
2 or x
3
→
u
2, say, x
2
→
u
2, then u
2
⇒
(
{
x
3
,
v
2
}
∪
V
(
C
3
)
) and x
3
→
(
{
v
2
}
∪
V
(
C
3
)
). Since i
l
(
D
)
≤
1, x
2
→
u
3 or x
2
→
v
3. In the former case there exist two complementary cycles x
3
v
2
u
1
x
3 and w
1
x
2
u
3
x
1
w
2
u
2
v
3
w
3
v
1
w
1, and in the latter case two complementary cycles are x
3
v
2
u
1
x
3 and w
1
x
2
v
3
x
1
w
2
u
2
w
3
u
3
v
1
w
1.
Ifu
2
→
{
x
2
,
x
3
}, then {
x
2
,
x
3
}
→
(
{
v
2
}
∪
V
(
C
3
)
). In addition, if u
2
→
v
2, we have the complementary cycles u
2
v
2
x
1
u
2 and w
1
x
2
u
3
v
1
w
2
x
3
v
3
w
3
u
1
w
1; if v
2
→
u
2 and there exists an arc from Y to Z, say, w
1
→
v
2, then we have the complementary cycles C
1
=
w
1
v
2
x
1
w
1 and C
2
=
x
2
u
3
v
1
w
2
u
2
x
3
v
3
w
3
u
1
x
2; if v
2
→
(
{
u
2
}
∪
Y
), then V
(
C
3
)
⇒
v
2, and we have the complementary cycles C
1
=
v
2
w
1
x
2
v
2 and C
2
=
w
2
u
2
x
3
u
3
v
3
w
3
x
1
u
1
v
1
w
2.
Now assume thatx
2
∉
R
2 or x
3
∉
R
2. Then Y
=
{
x
2
,
x
3
} and v
2
∈
R
2. Otherwise, there exists one vertex x
∈
R
2 such that d
D
-
(
x
)
≥
6, a contradiction. Therefore, let, without loss of generality, Z
=
{
w
1
}. Then we have R
2
=
{
u
2
,
v
2
,
w
2
}, (
Z
∪
V
(
C
3
)
)
⇒
{
x
1
,
u
1
}, and w
2
→
{
u
2
,
v
2
}. Let, without loss of generality, u
2
→
v
2. This leads to the contradiction d
D
-
(
v
2
)
≥
6.
(ii) Letv
1
→
x
1. Then v
2
∈
R
2 and (
Z
∪
V
(
C
3
)
)
⇒
v
1. Let, without loss of generality, u
2
→
v
2. If Y
=
{
w
1
,
w
2
}, let, without loss of generality, Z
=
{
x
2
}, x
3
∈
R
2; then v
2
→
x
3
→
u
2, R
2
⇒
(
V
(
C
3
)
∪
Z
), and (
Z
∪
V
(
C
3
)
)
⇒
R
1. It is evident that u
2
x
2
v
1
u
2 and w
1
x
3
w
3
x
1
w
2
v
2
u
3
v
3
u
1
w
1 are complementary cycles in D. If Y
=
{
x
2
,
x
3
}, let, without loss of generality, Z
=
{
w
1
}; then v
2
→
w
2
→
u
2. This leads to the contradiction d
D
+
(
w
2
)
≥
6.
(2) Assume that |
R
1
∩
V
4
|
=
2. Let, without loss of generality, R
1
=
{
x
1
,
x
2
,
u
1
} and Y
=
{
v
1
,
v
2
}.
(a) IfZ
=
{
x
3
}, then R
2
=
{
u
2
,
w
1
,
w
2
} and {
w
1
,
w
2
}
→
u
2. This leads to the contradiction d
D
-
(
u
2
)
≥
6.
(b) IfZ
=
{
u
2
}, then R
2
=
{
x
3
,
w
1
,
w
2
}, {
w
1
,
w
2
}
→
x
3, R
2
⇒
(
V
(
C
3
)
∪
Z
), and (
V
(
C
3
)
∪
Z
)
⇒
R
1. This leads to the complementary cycles C
1
=
w
1
u
2
x
1
w
1 and C
2
=
v
1
w
2
u
3
x
2
v
2
x
3
v
3
w
3
u
1
v
1.
(c) If, without loss of generality,Z
=
{
w
1
}, then R
2
=
{
x
3
,
u
2
,
w
2
}, w
2
→
{
u
2
,
x
3
}, and u
2
→
x
3. This leads to R
2
⇒
(
V
(
C
3
)
∪
Z
) and (
V
(
C
3
)
∪
Z
)
⇒
R
1.
Ifu
1
→
x
1 or u
1
→
x
2, say, u
1
→
x
1, then x
2
⇒
u
1 and (
Z
∪
V
(
C
3
)
)
⇒
{
u
1
,
x
2
}. This leads to the complementary cycles C
1
=
u
2
w
1
x
1
u
2 and C
2
=
v
1
w
2
u
3
x
2
v
2
x
3
v
3
w
3
u
1
v
1.
If{
x
1
,
x
2
}
→
u
1, then Z
∪
V
(
C
3
)
⇒
{
x
1
,
x
2
}. This leads to the complementary cycles C
1
=
x
3
w
1
u
1
x
3 and C
2
=
v
1
u
2
v
3
w
3
x
1
v
2
w
2
u
3
x
2
v
1.
Thus we finish proof of case(
|
Z
|
,
|
Y
|
)
=
(
1,2
)
.
Case 3. One has |
Z
|
=
1 and |
Y
|
=
3. Then Y
=
V
4
=
{
x
1
,
x
2
,
x
3
}.
The case is equivalent to the case of “|
Y
|
=
2, x
3
∈
R
2, and x
3
→
R
2
∖
{
x
3
},” which has been proved in Case 2.


## 4. Concluding Remarks

In this paper, we proved the existence of complementary cycles in a kind of irregular multipartite tournaments. Problems on complementary cycles in irregular multidigraphs have important significance.In 2002, Volkmann gave a new type of connectivity condition for a multipartite tournament to be cycle complementary. They proposed the following conjecture.Conjecture 13 (see Volkmann [16] 2002).
LetD be a multipartite tournament. If k
(
D
)
≥
α
(
D
)
+
1, then D is cycle complementary, unless D is a member of a finite family of multipartite tournaments.In 2010, Li et al. [17] proved 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 T
7
1.The vertex set of a digraphD is denoted by V
(
D
). A c-partite tournament is an orientation of a complete c-partite graph. A multipartite tournament D is called weakly cycle complementary if there exist two vertex disjoint cycles C
1 and C
2 such that V
(
C
1
)
∪
V
(
C
2
) contains vertices of all partite sets of D. In 2008, Volkmann and Winzen [18] proved all 3-connected c-partite tournaments with c
≥
3 that are weakly cycle complementary. In 2011, He and Wang [19] proved all 3-partite tournaments that are weakly cycle complementary.In 2008, Volkmann and Winzen [18] also proposed the following problem.Problem 14 (see Volkmann and Winzen [18] 2008).
Characterize all2-strong c-partite tournaments D with c
≥
3 and |
V
(
D
)
|
≥
6 that are weakly cycle complementary.All these problems may stimulate our further study for complementary cycles of digraphs.



---

*Source: 5384190-2016-08-15.xml*