Mathematical Problems of Computer Science 58, 20–31, 2022.

doi:10.51408/1963-0089

UDC 519.1

On an Extension of the Ghouila-Houri Theorem

Samvel Kh. Darbinyan

Institute for Informatics and Automation Problems of NAS RA

e-mail: samdarbin@iiap.sci.am

Abstract

Let D be a 2-strong digraph of order n ≥ 8 such that for every vertex x ∈ V(D)\{z},
d(x) ≥ n and d(z) ≥ n − 4, where z is a vertex in V(D). We prove that:

If D contains a cycle passing through z of length equal to n − 2, then D is Hamil-
tonian.

We also give a new sufficient condition for a digraph to be Hamiltonian-connected.
Keywords: Digraphs, Hamiltonian cycles, Hamiltonian-connected, 2-strong.
Article info: Received 21 Aprile 2022; received in revised form 16 September 2022;
accepted 15 November 2022.
Acknowledgement: We thank the referees for their valuable comments and sugges-
tions that improved the presentation considerably.

1. Introduction

In this paper, we consider finite digraphs (directed graphs) without loops and multiple arcs.
The order of a digraph D is the number of its vertices. We shall assume that the reader
is familiar with the standard terminology on digraphs. Terminology and notations not
described below follow [1]. Every cycle and path is assumed simple and directed. A cycle
(path) in a digraph D is called Hamiltonian (Hamiltonian path) if it includes every vertex
of D. A digraph D is Hamiltonian if it contains a Hamiltonian cycle, and it is Hamiltonian-
connected if for any pair of ordered vertices x and y there exists a Hamiltonian path from x
to y.

There are numerous sufficient conditions for the existence of a Hamiltonian cycle in a
digraph (see, [1]–[3]). Let us recall the following sufficient conditions for a digraph to be
Hamiltonian.

Theorem 1: (Ghouila-Houri [4]). Let D be a strong digraph of order n ≥ 2. If for every
vertex x ∈ V(D), d(x) ≥ n, then D is Hamiltonian.

Theorem 2: (Meyniel [5]). Let D be a strong digraph of order n ≥ 2. If d(x)+d(y) ≥ 2n−1
for all pairs of non-adjacent vertices x and y in D, then D is Hamiltonian.

Nash-Williams [6] raised the problem of describing all the extreme digraphs in Theorem 1,
that is, all digraphs with minimum degree at least |D| − 1, that do not have a Hamiltonian

20



S. Darbinyan 21

cycle. As a solution to this problem, Thomassen [7] proved a structural theorem on the
extreme digraphs. An analogous problem for Theorem 2 was considered by the author [8]. In
[8], we generalize Thomassen’s structural theorem (Theorem 1, in [7]), characterizing the non-
Hamiltonian strong digraphs of order n with the degree condition that d(x) + d(y) ≥ 2n − 2
for every pair of non-adjacent distinct vertices x, y. Moreover, in [8], it was also proved that
if m is the length of a longest cycle in D, then D contains cycles of all lengths k = 2, 3, . . . , m.
The following conjecture was suggested by Thomassen.

Conjecture 1: (Thomassen [9], see Conjecure 1.6.7 in [2]). Every 3-strong digraph of order
n and with minimum degree at least n + 1 is Hamiltonian-connected.

In [10], we disprove this conjecture, by proving the following three theorems.

Theorem 3: Every k-strong (k ≥ 1) digraph of order n, which has n − 1 vertices of degrees
at least n, is Hamiltonian if and only if any (k + 1)-strong digraph of order n + 1 with
minimum degree at least n + 2 is Hamiltonian-connected.

Theorem 4: For every n ≥ 8, there is a non-Hamiltonian 2-strong digraph D of order n
with minimum degree equal to 4 such that D has n − 1 vertices of degrees at least n.

Theorem 5: For every n ≥ 9, there exists a 3-strong digraph D of order n with minimum
degree at least n+1 such that D contains two distinct vertices u, v for which u ↔ v, d+D(u)+
d−D(v) = 6 and there is no (u, v)-Hamiltonian path.

In view of Theorems 4, 5 and Conjecture 1, it is natural to pose the following problem.

Problem: Let D be a 2-strong digraph of order n ≥ 9. Suppose that n − 1 vertices of D
have degrees at least n and a vertex x has degree is at least n − m, where 1 ≤ m ≤ n − 5.
Find the maximum value of m, for which D is Hamiltonian.

Goldberg, Levitskaya and Satanovskiy [11] relaxed the conditions of the Ghouila-Houri
theorem. They proved the following theorem.

Theorem 6: (Goldberg et al. [11]). Let D be a strong digraph of order n ≥ 2. If for every
vertex x ∈ V(D) \ {z}, d(x) ≥ n and d(z) ≥ n − 1, then D is Hamiltonian.

Note that Theorem 6 is an immediate consequence of Theorem 2. In [11], the authors for
any n ≥ 5 presented two examples of non-Hamiltonian strong digraphs of order n such that:

(i) In the first example, n − 2 vertices have degrees equal to n + 1 and the other two
vertices have degrees equal to n − 1.

(ii) In the second example, n−1 vertices have degrees at least n and the remaining vertex
has degree equal to n − 2.

In [12], it was reported that the following theorem holds.

Theorem 7: (Darbinyan [12]). Let D be a 2-strong digraph of order n ≥ 9 with minimum
degree at least n − 4. If n − 1 vertices of D have degrees at least n, then D is Hamiltonian.

In this article, we present the first part of the proof of Theorem 7, which we formulate as
Theorem 9. The proof of the last theorem has never been published. It is worth mentioning
that the proof presented here differs from the previous handwritten proof and is significantly
shorter and more general than the previous one. The second part of the proof (i.e., the
complete proof) of Theorem 7 we will present in the forthcoming paper, where we also



22 On an Extension of the Ghouila-Houri Theorem

present two examples of digraphs, which show that the bounds n ≥ 9 and n − 4 in Theorem
7 are sharp in a sense.

2. Further Terminology and Notation

For the sake of clarity we repeat the most impotent definition. The vertex set and the arc set
of a digraph D are denoted by V(D) and A(D), respectively. The order of a digraph D is the
number of its vertices. The converse digraph of D is the digraph obtained from D by reversing
the direction of all arcs. The arc of a digraph D directed from x to y is denoted by xy or
x → y (we also say that x dominates y or y is an out-neighbour of x and x is an in-neighbour of
y), and x ↔ y denotes that x → y and y → x (x ↔ y is called 2-cycle). If x → y and y → z,
we write x → y → z. If A and B are two disjoint subsets of V(D) such that every vertex of
A dominates every vertex of B, then we say that A dominates B, denoted by A → B. We
define A(A → B) = {xy ∈ A(D) | x ∈ A, y ∈ B} and A(A, B) = A(A → B) ∪ A(B → A).
If x ∈ V(D) and A = {x} we sometimes write x instead of {x}. Let N+D(x), N

−
D(x) denote

the set of out-neighbors, respectively the set of in-neighbors of a vertex x in a digraph
D. If A ⊆ V(D), then N+D(x, A) = A ∩ N

+
D(x) and N

−
D(x, A) = A ∩ N

−
D(x). The out-

degree of x is d+D(x) = |N
+
D(x)| and d

−
D(x) = |N

−
D(x)| is the in-degree of x. Similarly,

d+D(x, A) = |N
+
D(x, A)| and d

−
D(x, A) = |N

−
D(x, A)|. The degree of the vertex x in D is

defined as dD(x) = d
+
D(x) + d

−
D(x) (similarly, dD(x, A) = d

+
D(x, A) + d

−
D(x, A)). We omit the

subscript if the digraph is clear from the context. The subdigraph of D induced by a subset
A of V(D) is denoted by D. In particular, D − A = D⟨V(D) \ A⟩. For integers a and b,
a ≤ b, by [a, b] we denote the set {xa, xa+1, . . . , xb}. If j < i, then {xi, . . . , xj} = ∅.

The path (respectively, the cycle) consisting of the distinct vertices x1, x2, . . . , xm (m ≥ 2)
and the arcs xixi+1, i ∈ [1, m − 1] (respectively, xixi+1, i ∈ [1, m − 1], and xmx1), is denoted
by x1x2 · · · xm (respectively, x1x2 · · · xmx1). The length of a cycle or a path is the number
of its arcs. Let D be a digraph and z ∈ V(D). By Cm(z) (respectively, C(z)) we denote a
cycle in D of length m (respectively, any cycle in D), which contains the vertex z. We say
that P = x1x2 · · · xm is a path from x1 to xm or is an (x1, xm)-path. A digraph D is strong
(strongly connected) if, for every pair x, y of distinct vertices in D, there exists an (x, y)-path
and a (y, x)-path. A digraph D is k-strong (k-strongly connected) if, |V(D)| ≥ ∥ + ∞ and
for any set A of at most k − 1 vertices D − A is strong. Two distinct vertices x and y are
adjacent if xy ∈ or yx ∈ A(D) (or both). The converse digraph of D is the digraph obtained
from D by replacing the direction of all arcs. We will use the principle of digraph duality:
Let D be a digraph, then D contains a subdigraps H if and only if the converse digraph of
D contain the converse of subdigraph H.

3. Preliminaries

In our proofs, we will use the following well-known simple lemma.

Lemma 1: (Häggkvist and Thomassen [13]). Let D be a digraph of order n ≥ 3 containing
a cycle Cm of length m, m ∈ [2, n − 1]. Let x be a vertex not contained in this cycle. If
d(x, V(Cm)) ≥ m + 1, then for every k ∈ [2, m + 1], D contains a cycle Ck including x.

The next lemma is a slight modification of a lemma by Bondy and Thomassen [14], it is
very useful and will be used extensively throughout this paper.



S. Darbinyan 23

Lemma 2:. Let D be a digraph of order n ≥ 3 containing a path P := x1x2 . . . xm, m ∈
[2, n − 1]. Let x be a vertex not contained in this path. If one of the following condition
holds:

(i) d(x, V(P)) ≥ m + 2,
(ii) d(x, V(P)) ≥ m + 1 and xx1 /∈ A(D) or xmx /∈ A(D),
(iii) d(x, V(P)) ≥ m and xx1 /∈ A(D) and xmx /∈ A(D),
then there is an i ∈ [1, m − 1] such that xi → x → xi+1, i.e., D contains a path

x1x2 . . . xixxi+1 . . . xm of length m (we say that x can be inserted into P).

Using Lemma 2, we can prove the following lemma.

Lemma 3: Let P := x1x2 . . . xm, m ∈ [3, n−1], be a longest (x1, xm)-path in a digraph D of
order n. Suppose that y ∈ V(D)\V(P) and there is no i ∈ [1, m−2] such that xi → y → xi+2.
Then the following holds:

(i) If yx1 /∈ A(D), x1y ∈ A(D) and d(y, V(P)) ≥ m, then d(y, V(P)) = m and
{x1, x2, . . . , xm} → y;

(ii) If xmy /∈ A(D), yxm ∈ A(D) and d(y, V(P)) ≥ m, then d(y, V(P)) = m and
y → {x1, x2, . . . , xm};

(iii) If d(y, V(P)) ≥ m+1, then d(y, V(P)) = m+1 and there exists an integer q ∈ [1, m]
such that {xq, xq+1, . . . , xm} → y → {x1, x2, . . . , xq}.

Proof. To prove the lemma, it suffices to show that every vertex xi ∈ V(P) is adjacent to y.
Assume that this is not the case. (i) Let y and xt be not adjacent. Then t ≥ 2 since x1 → y.
Since P is a longest (x1, xm)-path, we have that y cannot be inserted into P . Using Lemma
2(ii) and the assumption that yx1 /∈ A(D), we obtain xmy ∈ A(D), 2 ≤ t ≤ m − 1 and
m ≤ d(y, V(P)) = d(y, {x1, . . . , xt−1}) + d(y, {xt+1, . . . , xm}) ≤ t − 1 + (m − t + 1) = m.

This means that d(y, {x1, . . . , xt−1}) = t − 1 and d(y, {xt+1, . . . , xm}) = m − t + 1. Again
using Lemma 2, we obtain that xt−1 → y → xt+1, which contradicts the supposition of
Lemma 3. This contradiction shows that every vertex xi is adjacent to y.

In a similar way, one can show that if (ii) or (iii) holds, then every vertex of P also is
adjacent to y. Lemma 3 is proved.

In [10], the author proved the following theorem.

Theorem 8: (Darbinyan [12]). Let D be a strong digraph of order n ≥ 3. Suppouse that
d(x)+d(y) ≥ 2n−1 for all pairs of non-adjacent vertices x, y ∈ V(D)\{z}, where z is some
vertex in V(D). Then D is Hamiltonian or contains a cycle of length n − 1.

Using Theorem 8 and Lemmas 1 and 2, it is not difficult to show that the following
corollaries are true.

Corollary 1: Let D be a strong digraph of order n ≥ 3 satisfying the condition of Theorem
8. Then D has a cycle that contains all the vertices of D maybe except z.

Corollary 2: Let D be a strong digraph of order n ≥ 3. Suppose that n − 1 vertices of D
have degrees at least n. Then D is Hamiltonian or contains a cycle of length n − 1 (in fact,
D has a cycle that contains all the vertices of degrees at least n).

In this section, we also will prove the following lemma. We will use this lemma in the
second part of the proof of Theorem 7.



24 On an Extension of the Ghouila-Houri Theorem

Lemma 4: Let D be a digraph of order n ≥ 4 such that for any vertex x ∈ V(D)\{z}, d(x) ≥
n and d(z) ≤ n − 2, where z is some vertex in V(D). Suppose that Cm(z) = x1x2 . . . xmx1
with m ≤ n−2 is a longest cycle through z. If D⟨V (D)\V (Cm(z))⟩ is strong and D contains
a Cm(z)-bypass P = xiy1y2 . . . ylxj such that |V(Cm(z)[xi+1, xj−1])| is smallest possible over
all Cm(z)-bypasses, then z ∈ V(Cm(z)[xi+1, xj−1]).

Proof. Without loss of generality, we assume that xj = x1, xi = xm−k, k ≥ 1,
A({y1, . . . , yl}, V(Cm(z)[xm−k+1, xm])) = ∅ and k is minimum possible with this property
over all Cm(z)-bypasses. Extending the path Cm(z)[x1, xm−k] with the vertices of
V(Cm(z)[xm−k+1, xm]) as much as possible, we obtain an (x1, xm−k)-path, say R. Since
Cm(z) is a longest cycle through z, some vertices u1, u2, . . . , ud ∈ V(Cm(z)[xm−k+1, xm]),
1 ≤ d ≤ k, are not on the obtained extended path R. Using Lemma 2, we ob-
tain that d(yi, VV (Cm(z))) ≤ m − k + 1 and d(ui, V(Cm(z))) ≤ m + d − 1. Put
B := V(D) \ (V(Cm(z)) ∪ V(P)). Note that |B| = n − m − l. Let v be an arbitrary
vertex in B. From the minimality of k, we have that D contains no paths of the types
ui → v → yj and yj → v → ui, which in turn implies that d+(ui, B) + d−(yj, B) ≤ |B| and
d−(ui, B) + d

+(yj, B) ≤ |B|. Therefore, d(ui, B) + d(yj, B) ≤ 2|B| = 2(n − m − l). Thus, we
have

d(ui) + d(yj) = d(ui, V(Cm(z))) + d(yj, V(Cm(z))) + d(ui, B) + d(yj, B) + d(yj, {y1, . . . , yl})
≤ m + d − 1 + m − k + 1 + 2n − 2m − 2l + 2l − 2 = 2n − 2 − (k − d) ≤ 2n − 2.

This is possible if ui = z. Therefore, d = 1 and z ∈ V(Cm(z)[xm−k+1, xm]). Lemma 4 is
proved.

4. The Main Result

In this section, we prove the following theorem.

Theorem 9: Let D be a 2-strong digraph of order n ≥ 8. Suppose that for every x ∈
V(D) \ {z}, d(x) ≥ n and d(z) ≥ n − 4, where z is a vertex in V(D). If D contains a cycle
of length n − 2 passing through z (i.e., a cycle Cn−2(z)), then D is Hamiltonian.

Before we prove our main result, we will prove the following lemma.

Lemma 5: Let D be a non-Hamiltonian 2-strong digraph of order n such that for any
vertex x ∈ V(D) \ {z}, d(x) ≥ n and d(z) ≤ n − 2, where z is an arbitrary fixed vertex in
V(D). Suppose that Cm+1(z) = x1x2 . . . xmzx1 with m ∈ [2, n − 3] is a longest cycle in D,
d(z, Y ) = 0 and D⟨Y ⟩ is a strong digraph, where Y := V(D) \ V(Cm+1(z)). Let y1, y2 be two
distinct vertices in Y . If for each yi ∈ {y1, y2}, d(yi, {x1, x2, . . . , xm}) = m + 1, then n ≥ 6
and d(z) ≤ m − 2.

Proof. By contradiction, suppose that d(z) ≥ m−1. We denote by P the path x1x2 . . . xm.
Note that |Y | = n − m − 1. Since the path P cannot be extended with any vertex y ∈ Y ,
by Lemma 2, d(y, V(P)) ≤ m + 1 and

n ≤ d(y) = d(y, V(P)) + d(y, Y ) ≤ m + 1 + d(y, Y ), d(y, Y ) ≥ n − m − 1 = |Y |. (1)
Since D is 2-strong and Cm+1(z) is a longest cycle, using Lemma 2 and d(yi, V(P)) = m + 1
it is not difficult to show that there is an integer l ∈ [2, m − 1] such that

{xl, xl+1, . . . , xm} → {y1, y2} → {x1, x2, . . . , xl}. (2)



S. Darbinyan 25

Since d(y, Y ) ≥ n − m − 1 = |Y |(by (1)), and D⟨Y ⟩ is strong, by the Ghouila-Houri
theorem, D⟨Y ⟩ is Hamiltonian. Put E := {x1, x2, . . . , xl−1} and F := {xl+1, xl+2, . . . , xm}.
Since Cm+1(z) is a longest cycle and D⟨Y ⟩ is strong, from (2) it follows that

A(E → Y) = A(Y → F) = ∅. (3)

Note that from |Y | ≥ 2, |E| ≥ 1 and |F| ≥ 1 it follows that n ≥ 6. We need to prove the
following Claims 1-2 bellow.

Claim 1.
(i) If d−(z, E) ≥ 1, then d+(z, F) = 0.
(ii) A(E → F) ̸= ∅.

Proof. (i) By contradiction, suppose that xi ∈ E, xj ∈ F and xi → z → xj. Then by
(2), y1 → xi+1 and xj−1 → y2. Hence, Cm+3(z) = x1x2 . . . xizxj . . . xmy1xi+1 . . . xj−1y2x1, a
contradiction.

(ii) Suppose, on the contrary, that A(E → F) = ∅. Then using Claim 1(i) and (3), we
obtain: if d−(z, E) ≥ 1, then d+(z, F) = 0 and A(E ∪ Y ∪ {z} → F) = ∅, if d−(z, E) = 0,
then A(E ∪ Y → F ∪ {z}) = ∅. Therefore, D − xl is not strong, which contradicts that D
is 2-strong.

From now on, we assume that xaxb ∈ A(E → F). Note that 1 ≤ a ≤ l − 1 and
l + 1 ≤ b ≤ m. We may assume that b is the maximum and a is the minimum with these
properties. By (2), we have

xb−1 → {y1, y2} → xa+1. (4)

Since z cannot be inserted into P , using Lemma 2(ii) and Clam 1(i), we obtain

d(z, {x1, x2, . . . , xa}) + d(z, {xb, xb+1, . . . , xm}) ≤ a + m − b + 2. (5)

By R(yi, y3−i), where i ∈ [1, 2], we denote a longest (yi, y3−i)-path in D⟨Y ⟩. From now
on, assume that R(yi, y3−i) = R(y1, y2).

Claim 2.
(i) If i ∈ [a + 1, l − 1], then xiz /∈ A(D).
(ii) If j ∈ [l + 1, b − 1], then zxj /∈ A(D).
(iii) If i ∈ [a + 1, l] and i − a ≤ 2, then zxi /∈ A(D).
(iv) If j ∈ [l, b − 1] and b − j ≤ 2, then xjz /∈ A(D).

Proof. Each of claims (i)-(iv) we prove by contradiction.
(i) Assume that i ∈ [a + 1, l − 1] and xiz ∈ A(D). Then by (2) and (4), we have

Cm+3(z) = x1x2 . . . xaxb . . . xmy1xi+1 . . . xb−1y2xa+1 . . . xizx1, a contradiction.
(ii) Assume that j ∈ [l + 1, b − 1] and zxj ∈ A(D). Then by (2) and (4), we have

Cm+3(z) = x1x2 . . . xaxb . . . xmzxj . . . xb−1y1xa+1 . . . xj−1y2x1, a contradiction.
(iii) Assume that i ∈ [a + 1, l], i − a ≤ 2 and zxi ∈ A(D). Then C(z) = x1x2 . . . xaxb . . .

xmzxi . . . xb−1R(y1, y2)x1 is a cycle of length at least m + 2, a contradiction.
(iv) Assume that j ∈ [l, b − 1], b − j ≤ 2 and xjz ∈ A(D). Then C(z) = x1x2 . . . xaxb . . .

xmR(y1, y2)xa+1 . . . xjzx1 is a cycle of length at least m + 2, a contradiction. Claim 2 is
proved.



26 On an Extension of the Ghouila-Houri Theorem

Now we will consider the following cases depending on the values of a and b with respect
to l.

Case 1. a ≤ l − 3 and b ≥ l + 3.
Then by Claim 2, d(z, {xa+1, xa+2, xb−2, xb−1}) = 0. Therefore, since z cannot be inserted

into P , using (5) and Lemma 2, we obtain

m − 1 ≤ d(z, {x1, x2, . . . , xa, xb, xb+1, . . . , xm}) + d(z, {xa+3, . . . , xb−3})

≤ a + m − b + 2 + b − 3 − a − 2 + 1 = m − 2,

which is a contradiction.
Case 2. a ≤ l − 3 and b = l + 2.
Then by Claim 2, d(z, {xa+1, xa+2, xl+1}) = 0 and xlz /∈ A(D). Therefore, since z cannot

be inserted into P , using (5) and Lemma 2, we obtain

m − 1 ≤ d(z, {x1, x2, . . . , xa, xb, xb+1, . . . , xm}) + d(z, {xa+3, . . . , xl})

≤ a + m − b + 2 + l − a − 2 = m − (l + 2) + l = m − 2,

which is a contradiction.
Case 3. a ≤ l − 3 and b = l + 1.
Then by Claim 2, d(z, {xa+1, xa+2}) = 0 and xlz /∈ A(D). Similar to Case 2, we obtain

m − 1 ≤ d(z, {x1, x2, . . . , xa, xb, xb+1, . . . , xm}) + d(z, {xa+3, . . . , xl})

≤ a + m − b + 2 + l − a − 2 = m − b + l = m − (l + 1) = m − 1.

This implies that d(z, {xa+3, . . . , xl}) = l − a − 2. Hence, by Claim 2(i) and xlz /∈ A(D),
z → {xa+3, . . . , xl}. From this and (4), we see that the cycle Q(z) = x1x2 . . . xaxb . . . xmz
xa+3 . . . xlR(y1, y2)x1 has length equal to m − 1 + |V(R(y1, y2))|. Since Cm+1(z) is a longest
cycle and D⟨Y ⟩ is Hamiltonian, it follows that |V(R(y1, y2))| = |Y | = 2. Then m = n − 3,
y1 ↔ y2, xa+1 ↔ xa+2 and xa+1 (xa+2) is adjacent to each vertex xi ∈ {x1, x2, . . . xm}, as
d(xa+1) ≥ n (d(xa+2) ≥ n) and xa+1 (xa+2) cannot be inserted into Q(z).

We will distinguish two subcases.
Subcase 3.1. m ≥ l + 2. From the minimality of a and the maximality of b, it follows

that

A({x1, x2, . . . , xa} → {xb+1, xb+2, . . . , xm}) = ∅. (6)

Assume that xi → xj with i ∈ [a + 1, l] and j ∈ [l + 2, m]. Using (4) and the
fact that zxa+3 ∈ A(D), it is not difficult to see that if i ∈ [a + 1, a + 2], then
C(z) = x1x2 . . . xa+1(xa+2)xj . . . xmzxa+3 . . . xj−1y1y2x1 is a cycle of length at least m + 2,
if i ∈ [a + 3, l − 1], then Cm+3(z) = x1x2 . . . xixj . . . xmzxi+1 . . . xj−1y1y2x1, if i = l, then
Cm+3(z) = x1x2 . . . xaxl+1 . . . xj−1y1y2xa+1 . . . xlxj . . . xmzx1. Thus, in all cases, we have a
contradiction. We may, therefore, assume that (recall that b = l + 1)

A({xa+1, xa+2, . . . , xl} → {xb+1, xb+2, . . . , xm}) = ∅.

Combining this with (6), we obtain

A({x1, x2, . . . , xl} → {xb+1, xb+2, . . . , xm}) = ∅. (7)



S. Darbinyan 27

Assume first that d−(z, E) ≥ 1. Then by Claim 1(i), d+(z, F) = 0. This together
with (3) and (7) implies that A({z, x1, x2, . . . , xl} ∪ Y → {xl+2, xl+3, . . . , xm}) = ∅. As-
sume second that d−(z, E) = 0. Since xlz /∈ A(D), we obtain A({x1, x2, . . . , xl} ∪ Y →
{z, xl+2, xl+3, . . . , xm}) = ∅. So, in both cases we have that the subdigraph D − xl+1 is not
strong, which contradicts that D is 2-strong.

Subcase 3.2. b = l + 1 = m.
Assume that a ≥ 2. As mentioned above, either x1 → xa+1 or xa+1 → x1. Therefore,

Cm+3(z) = x1xa+1 . . . xm−1y1y2x2 . . . xaxmzx1 or Cm+2(z) = x1 . . . xaxmzxa+3 . . . xm−1y1y2
xa+1x1. So, in both cases, we have a contradiction.

Assume next that a = 1. Then from d−(z, {x2, x3, . . . , xm−1}) = 0 (by Claims 2(i) and
2(iv)) and d−(z) ≥ 2 it follows that x1 → z. We know that z → {xa+3, . . . , xl}. Using this,
it is not difficult to see that if xi → xm with i ∈ [2, m − 2], then for i = 2, Cm+2(z) =
x1x2xmzx4 . . . xm−1y1y2x1, and for i ∈ [3, m − 2], Cm+3(z) = x1x2 . . . xixmzxi+1 . . . xm−1y1
y2x1, a contradiction. We may, therefore, assume that

d−(xm, {x2, x3, . . . , xm−2}) = 0. (8)

Now we consider the vertex x1. If xj → x1 with j ∈ [2, m − 2], then for j = 2, Cm+2(z) =
x1xmzx4 . . . xm−1y1y2x2x1, and for j ∈ [3, m − 2], Cm+3(z) = x1xmzxj+1 . . . xm−1y1y2x2 . . .
xjx1. Thus, in both cases, we have a contradiction. We may, therefore, assume that
d−(x1, {x2, x3, . . . , xm−2}) = 0. This together with (3), (8) and d−(z, {x2, x3, . . . , xm−1}) = 0
implies that

A({x2, x3, . . . , xm−2} → Y ∪ {z, x1, xm}) = ∅.

This means that D − xm−1 is not strong, which contradicts that D is 2-strong.
Case 4. a = l − 2. Taking into account Case 2 and the digraph duality, we may assume

that b ≤ l + 2.
Subcase 4.1. a = l − 2 and b = l + 2. Then by Claim 2, d(z, {xl−1, xl, xl+1}) = 0. This

together with (5) implies that

m − 1 ≤ d(z, {x1, x2, . . . , xa, xb, xb+1, . . . , xm}) ≤ a + m − b + 2

= m + l − 2 − l − 2 + 2 = m − 2,

a contradiction.
Subcase 4.2. a = l − 2 and b = l + 1. Then by Claim 2, d(z, {xl−1, xl}) = 0.
Assume first that m ≥ l + 2. If there exist i ∈ [l − 1, l] and j ∈ [l + 2, m] such

that xi → xj, then C(z) = x1x2 . . . xl−2xl+1 . . . xj−1R(y1, y2)xixj . . . xmzx1 is a cycle of
length at least m + 2, a contradiction. We may, therefore, assume that A({xl−1, xl} →
{xl+2, xl+3, . . . , xm}) = ∅. This together with (3), the minimality of a and the maximality of b
implies that A({x1, x2, . . . , xl} → {xl+2, xl+3, . . . , xm}) = ∅. Therefore, if d−(z, E) = 0, then
A({x1, x2, . . . , xl}∪Y → {z, xl+2, xl+3, . . . , xm}) = ∅, and if d−(z, E) ≥ 1, then d+(z, F) = 0
(Claim 1(i)) and A({z, x1, x2, . . . , xl} ∪ Y → {xl+2, xl+3, . . . , xm}) = ∅. Thus, in both cases,
we have that D − xl+1 is not strong, a contradiction.

Assume next that m = l + 1. Then a = l − 2 = m − 3. Let a ≥ 2. From
the minimality of a it follows that d−(xm, {x1, x2, . . . , xa−1}) = 0. If there exist i ∈
[1, a − 1] and j ∈ [a + 1, a + 2] such that xi → xj, then it is easy to see that C(z) =
x1x2 . . . xixj . . . xm−1R(y1, y2)xi+1 . . . xaxmzx1 is a cycle of length at least m+2, a contradic-
tion. We may, therefore, assume that A({x1, x2, . . . , xa−1} → {xa+1, xa+2, xa+3 = xm}) = ∅.



28 On an Extension of the Ghouila-Houri Theorem

From this we have: if d−(z, {x1, x2, . . . , xa−1) = 0, then

A({x1, x2, . . . , xa−1} → Y ∪ {z, xa+1, xa+2, xa+3}) = ∅,

if d−(z, {x1, x2, . . . , xa−1) ≥ 1, then by Claim 1(i), zxm /∈ A(D) and

A({x1, x2, . . . , xa−1} ∪ {z} → Y ∪ {xa+1, xa+2, xa+3}) = ∅.

So, in both cases, we have that D − xa is not strong, which contradicts that D is 2-strong.
Let now a = 1. Then m = 4 = b = l + 1 and d(z, {x2, x3}) = 0. This together with
d(z, Y ) = 0, d+(z) ≥ 2 and d−(z) ≥ 2 implies that x1 → z → x4, which contradicts Claim
1(i).

Case 5. a = l − 1. Taking into account Cases 3 and 4, we may assume that b = l + 1.
Then d(z, {xl}) = 0, and from (3), the minimality of a and the maximality of b it follows
that

A({x1, x2, . . . , xl−1} → Y ∪ {xl+2, xl+3, . . . , xm})

= A({x1, x2, . . . , xl−2} → Y ∪ {xl+1, xl+2, . . . , xm}) = ∅. (9)

It is not difficult see that: if xl → xj with j ∈ [l + 2, m], then C(z) = x1x2 . . . xl−1xl+1 . . .
xj−1R(y1, y2)xlxj . . . xmzx1 is a cycle of length at least m + 3, if xi → xl with i ∈ [1, l − 2],
then C(z) = x1x2 . . . xixlR(y1, y2)xi+1 . . . xl−1xl+1 . . . xmzx1 is a cycle of length at least
m + 3. So, in both cases we have a contradiction. We may, therefore, assume that
d+(xl, {xl+2xl+3, . . . , xm}) = d−(xl, {x1, . . . , xl−2}) = 0. Then by (9),

A({x1, x2, . . . , xl−2} → {xl, xl+1, . . . , xm})

= A({x1, x2, . . . , xl} → {xl+2, xl+3, . . . , xm}) = ∅. (10)

Assume that m ≥ l + 2. If d−(z, E) ≥ 1, then d+(z, F) = 0 (Claim 1(i)). This together
with (3), (10), d(z, {xl}) = 0 and d(z, Y ) = 0 implies that A({z, x1, x2, . . . , xl} ∪ Y →
{xl+2, xl+3, . . . , xm}) = ∅, which in turn implies that D − xl+1 is not strong, a contradiction.
We may, therefore, assume that d−(z, E) = 0. Now it is not difficult to see that

A({x1, x2, . . . , xl} ∪ Y → {z, xl+2, xl+3, . . . , xm}) = ∅.

This means that D − xl+1 is not strong, a contradiction.
Assume now that m = l + 1. By the digraph duality, we may assume that a = l − 1 = 1.

Hence, b = l + 1 = m = 3. Then, since d+(z) ≥ 2 and d−(z) ≥ 2, x1 → z → xm, which
contradicts Claim 1(i). The discussion of Case 5 is completed. Lemma 5 is proved.

Now we are ready to prove the main result. For the convenience of the reader, we restate
it here.

Theorem 9: Let D be a 2-strong digraph of order n ≥ 8 and z be a fixed vertex in V(D).
Suppose that for any vertex x ∈ V(D) \ {z}, d(x) ≥ n, d(z) ≥ n − 4, and D contains a cycle
of length n − 2 passing through z. Then D is Hamiltonian.

Proof. Suppose, on the contrary, that D contains a cycle Cn−2(z) := x1x2 . . . xn−2x1 but
it is not Hamiltonian. By Theorem 3 (or by Theorem 2), d(z) ≤ n − 2. Let {y1, y2} =
V(D) \ V(Cn−2(z)). Since z ∈ V(Cn−2(z)), we have that d(yi) ≥ n. Using Lemma 1,
it is easy to show that D contains no Cn−1(z), d(y1) = d(y2) = n, d(y1, V(Cn−2(z))) =



S. Darbinyan 29

d(y2, V(Cn−2(z))) = n − 2 and y1 ↔ y2. If y1 or y2 is adjacent to every vertex xi, i ∈
[1, n − 2], then D contains a cycle C(z) of length at least n − 1, a contradiction. We
may, therefore, assume that y1 and some vertex of Cn−2(z) are not adjacent, say xn−2.
Then d(y1, {x1, x2, . . . , xn−3}) = n − 2. Since y1 cannot be inserted into x1x2 . . . xn−3, using
Lemma 2, we obtain that xn−3 → y1 → x1. This together with y1 ↔ y2 implies that
d(xn−2, {y1, y2}) = 0 (for otherwise, D contains a cycle of length at least n − 1 through z,
which is a contradiction). Therefore, d(y2, {x1, x2, . . . , xn−3}) = n − 2, and by Lemma 2,
xn−3 → y2 → x1. Then Cn−1 = x1x2 . . . xn−3y1y2x1 is a cycle of length n − 1. We know that
Cn−1 does not contain the vertex z. Therefore, z = xn−2. Thus, we have that the conditions
of Lemma 5 hold. Therefore, d(z) ≤ n−5, which contradicts that d(z) ≥ n−4. The theorem
is proved.

In [15], Overbeck-Larisch proved the following sufficient condition for a digraph to be
Hamiltonian-connected.

Theorem 10: (Overbeck-Larisch [15]). Let D be a 2-strong digraph of order n ≥ 3 such
that, for each two non-adjacent distinct vertices x, y we have d(x) + d(y) ≥ 2n + 1. Then for
each two distinct vertices u, v with d+(u) + d−(v) ≥ n + 1 there is a Hamiltonian (u, v)-path.

Let D be a digraph of order n ≥ 3 and let u and v be two distinct vertices in V(D).
Follows Overbeck-Larisch [15], we define a new digraph HD(u, v) as follows: V(HD(u, v)) =
V(D−{u, v})∪{z} (z a new vertex) and A(HD(u, v)) = A(D−{u, v})∪{zy | y ∈ N+D−v(u)}∪
{yz | y ∈ N−D−u(v)}.

Now, using Theorem 7, we will prove the following theorem, which is an analogue of the
Overbeck-Larisch theorem.

Theorem 11: Let D be a 3-strong digraph of order n + 1 ≥ 10 with minimum degree at
least n + 2. If for two distinct vertices u, v, d+D(u) + d

−
D(v) ≥ n − 2 or d

+
D(u) + d

−
D(v) ≥ n − 4

with uv /∈ A(D), then there is a Hamiltonian (u, v)-path in D.

Proof. Let D be a 3-strong digraph of order n + 1 ≥ 10 and let u, v be two distinct vertices
in V(D). Suppose that D and u, v satisfy the degree conditions of the theorem. Now we
consider the digraph H := HD(u, v) of order n ≥ 9. By an easy computation, we obtain
that the minimum degree of H is at least n − 4, and H has n − 1 vertices of degrees at
least n. Moreover, we know that H is 2-strong (see [10]). Thus, the digraph H satisfies
the conditions of Theorem 7. Therefore, H is Hamiltonian, which in turn implies that in D
there is a Hamiltonian (u, v)-path.

5. Conclusion

For Hamiltonicity of a graph G (undirected graph), there are numerous sufficient conditions
in terms of the number k(G) of connectivity, where k(G) ≥ 3 (recall that for a graph G to
be Hamiltonian, k(G) ≥ 2 is a necessary condition) and the minimum degree δ(G) (or the
sum of degrees of some vertices with certain properties), see the survey papers by Gould,
e.g. [16]. This is not the case for the general digraphs. In [17], the author proved that:
For every pair of integers k ≥ 2 and n ≥ 4k + 1 (respectively, n = 4k + 1), there exists a
k-strong (n−1)-regular (respectively, with minimum degree at least n−1 and with minimum
semi-degrees at least 2k −1 = (n−3)/2) a non-Hamiltonian digraph of order n. In [1] (Page



30 On an Extension of the Ghouila-Houri Theorem

253), it was showed that there is no k such that every k-strong multipartite tournament with
a cycle factor has Hamiltonian cycle.

Based on the evidence from Theorem 9, we raise the following conjecture, the truth of
which in the case k = 0 follows from Theorem 9.

Conjecture 2: Let D be a 2-strong digraph of order n and z be a fixed vertex in V(D).
Suppose that for any vertex x ∈ V(D) \ {z}, d(x) ≥ n + k and d(z) ≥ n − k − 4, where k ≥ 0
is an integer. Then D is Hamiltonian.

References

[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer,
2000.

[2] J.-C. Bermond and C. Thomassen, “Cycles in digraphs – A survey”, Journal of Graph
Theory, vol. 5, no. 1, pp. 1-43, 1981.

[3] D. Kühn and D. Osthus, “A survey on Hamilton cycles in directed graphs”, European
Journal of Combinatorics, vol. 33, pp. 750-766, 2012.

[4] A. Ghouila-Houri, “Une condition suffisante d’existence d’un circuit hamiltonien”,
Comptes Rendus de I’Academie des Sciences Paris, ser. A-B 251, pp. 495-497, 1960.

[5] M. Meyniel, “Une condition suffisante d’existence d’un circuit hamiltonien dans un
graphe oriente”, Journal of Combinatorial Theory, Ser. B, vol. 14, pp. 137-147, 1973.

[6] C.St.J.A. Nash-Williams, “Hamilton circuits in graphs and digraphs”, The many facets
of graph theory, Springer Verlag Lecture Notes 110, (Springer Verlag) pp. 237-243, 1969.

[7] C. Thomassen, “Long cycles in digraphs”, Proceedings of London Mathematical Society,
vol. 42, no. 3, pp. 231-251, 1981.

[8] S.Kh. Darbinyan, “Cycles of any length in digraph with large semi-degrees”, Aakdemy
Nauk Armyan SSR Doklady, (arXiv.1911.05998v1) vol. 75, no. 4, pp. 147-152, 1982 .

[9] C. Thomassen, “Long cycles in digraphs with constraints on degrees, Survey in Com-
binatorics”, Proc. 7th British Combinatorial Conf., London Math. Soc. Lecture Notes,
Cambridge University Press, vol. 38, pp. 211-228, 1979.

[10] S.Kh. Darbinyan, “Hamiltonian and strongly Hamilton-Connected digraphs”, Aakdemy
Nauk Armyan SSR Doklady, (arXiv.1801.05166v1), vol. 91, no. 1, pp. 3-8, 1990.

[11] M.K. Goldberg, L.P. Levitskaya and L.M. Satanovskiy, “On one strengthening of the
Ghouila-Houri theorem”, Vichislitelnaya Matematika i Vichislitelnaya Teknika, vol. 2,
pp. 56-61, 1971.

[12] S.Kh. Darbinyan, “A sufficient condition for a digraph to be Hamiltonian”, Aakdemy
Nauk Armyan SSR Doklady, vol. 91, no. 2, pp. 57-59, 1990.

[13] R. Häggkvist and C. Thomassen, “On pancyclic digraphs”, Journal of Combinatorial
Theory, Ser. B, vol. 20, no. 1, pp. 20-40, 1976.

[14] J.A. Bondy and C. Thomassen, “A short proof of Meyniel’s theorem”, Discrete Mathe-
matics, vol. 19, pp. 195-197, 1977.

[15] M. Overbeck-Larisch, “Hamiltonian pats in oriented graphs”, Journal of Combinatorial
Theory, Ser. B, vol. 21, pp. 76-80, 1976.



S. Darbinyan 3 1

[1 6 ] R .J. Go u ld , \ R e s e n t A d va n c e s o n t h e H a m ilt o n ia n P r o b le m : S u r ve y III" , Graphs and
Combinatorics, vo l. 3 0 , p p . 1 -4 6 , 2 0 1 4 .

[1 7 ] S .K h . D a r b in ya n , \ D is p r o o f o f a c o n je c t u r e o f Th o m a s s e n " , Aakdemy Nauk Armyan
SSR D oklady, vo l. 7 6 , n o . 2 , p p . 5 1 -5 4 , 1 9 8 3 .

¶áõÑÇɳ-ÐáõñÇÇ Ã»áñ»ÙÇ ÙÇ ÁݹɳÛÝÙ³Ý Ù³ëÇÝ

ê³Ùí»É Ê. ¸³ñµÇÝÛ³Ý

ÐÐ ¶²² ÆÝýáñÙ³ïÇϳÛÇ ¨ ³íïáÙ³ï³óÙ³Ý åñáµÉ»ÙÝ»ñÇ ÇÝëïÇïáõï

e-mail: samdarbin@iiap.sci.am

²Ù÷á÷áõÙ

Ü»ñϳ ³ß˳ï³ÝùáõÙ ³å³óáõóí»É ¿ Ñ»ï¨Û³É ûáñ»ÙÁ:
»áñ»Ù: ¸Çóáõù D-Ý 2-áõÅ»Õ Ï³å³Ïóí³Í n-·³·³Ã³ÝÇ (n ¸ 8 ) ÏáÕÙÝáñáßí³Í ·ñ³ý

¿, áñÇ n ¡ 1 ·³·³ÃÝ»ñÇ ³ëïÇ׳ÝÝ»ñÁ ÷áùñ ã»Ý n ÃíÇó, ÇëÏ z ·³·³ÃÇ ³ëïÇ׳ÝÁ
÷áùñ ã¿ n ¡ 4 ÃíÇó: ºÃ» D-Ý Ý å³ñáõݳÏáõÙ ¿ n ¡ 2 »ñϳñáõÃÛ³Ùµ óÇÏÉ, áñÁ ³ÝóÝáõÙ ¿

Ù³ïñÇó, ïÛáåÉÇóÛ³Ý Ù³ïñÇó:

Îá îäíîì ðàñøèðåíèè òåîðåìû Ãóéÿ-Óðè

Ñàìâåë Õ. Äàðáèíÿí

Èíñòèòóò ïðîáëåì èíôîðìàòèêè è àâòîìàòèçàöèè ÍÀÍ ÐÀ
e-mail: samdarbin@iiap.sci.am

Àííîòàöèÿ

 íàñòîÿùåé ðàáîòå äîêàçàíà ñëåäóþùàÿ òåîðåìà. Òåîðåìà. Ïóñòü D åñòü
2-ñèëüíî ñâÿçíûé n ¸ 8 âåðøèííûé îðãðàô, â êîòîðîì n ¡ 1 âåðøèí èìåþò
ñòåïåíü íå ìåíüøå ÷åì n , à âåðøèíà z èìååò ñòåïåíü íå ìåíüøå ÷åì n ¡ 4 . Åñëè
D ñîäåðæèò êîíòóð äëèíû n ¡ 2 , êîòîðèé ñîäåðæèò âåðøèíó z, òî D ñîäåðæèò
ãàìèëüòîíîâ êîíòóð.

Êëþ÷åâûå ñëîâà: îðãðàô, ãàìèëüòîíîâ êîíòóð, 2-ñèëüíî, ãàìèëüòîíîâî-
ñâÿçíûèé.

z ·³·³Ãáí, ³å³ D å³ñáõݳÏáõÙ ¿ ѳÙÇÉïáÝÛ³Ý óÇÏÉ:
´³Ý³ÉÇ µ³é»ñ` ѳϳ¹³ñÓ Ù³ïñÇó, »ñ»ù³ÝÏÛáõݳ·Í³ÛÇÝ Ù³ïñÇó, Ñ»ñÙÇïÛ³Ý


	02_Darbinyan_20_31
	02