Mathematical Problems of Computer Science 54, 7–17, 2020.

UDC 519.1

A Note on Hamiltonian Bypasses in Digraphs with

Large Degrees

Samvel Kh. Darbinyan

Institute for Informatics and Automation Problems of NAS RA

e-mail: samdarbin@iiap.am

Abstract

Let D be a 2-strongly connected directed graph of order p ≥ 3. Suppose that
d(x) ≥ p for every vertex x ∈ V (D)\{x0}, where x0 is a vertex of D. In this paper, we
show that if D is Hamiltonian or d(x0) > 2(p − 1)/5, then D contains a Hamiltonian
path, in which the initial vertex dominates the terminal vertex.

Keywords: Digraph, cycle, Hamiltonian cycle, Hamiltonian bypass.

1. Introduction

In this paper, we consider finite digraphs (directed graphs) without loops and multiple arcs.
Every cycle and path are assumed to be simple and directed. We shall assume that the reader
is familiar with the standard terminology on digraphs and refer the reader to [1]. A cycle
(path) in a digraph D passing through all the vertices of D is called Hamiltonian. A digraph
containing a Hamiltonian cycle is called a Hamiltonian digraph. A Hamiltonian path in a
digraph D in which the initial vertex dominates the terminal vertex is called a Hamiltonian
bypass. There are numerous sufficient conditions for the existence of a Hamiltonian cycle in
digraphs (see, e.g., [1, 2, 3]). It is natural to consider an analogous problem for the existence
of a Hamiltonian bypass.

It was proved in [4] - [9] that a number of sufficient conditions for a digraph to be Hamil-
tonian is also sufficient for a digraph to contain a Hamiltonian bypass (with some exceptions
which are characterized). In particular, Theorems 1.4 and 1.5 were proved in [5] and [6],
respectively. To formulate these theorems, we need the following definitions.

Definition 1: Let D0 denote any digraph of order p ≥ 3, p is odd, such that V (D0) = A∪B,
where A∩B = ∅, A is an independent set with (p + 1)/2 vertices, B is a set of (p−1)/2 ver-
tices inducing an arbitrary subdigraph, and D0 contains all the possible arcs between A and B.

Definition 2: For any k ∈ [1, p − 2] let Dp−k,k denote a digraph of order p ≥ 3, obtained
from K∗p−k and K

∗
k+1 by identifying a vertex of the first with a vertex of the second.

7



8 A Note on Hamiltonian Bypasses in Digraphs with Large Degrees

Definition 3: By T5 we denote a tournament of order 5 with vertex set {x1, x2, x3, x4, y}
and arc set {xixi+1 |i ∈ [1, 3]}∪{x4x1, x1y, x3y, yx2, yx4, x1x3, x2x4}.

Theorem 1: (Benhocine [5]). Let D be a 2-strong digraph of order p with minimum degree
at least p− 1. Then D contains a Hamiltonian bypass, unless D is isomorphic to a digraph
of type D0.

Theorem 2: (Darbinyan [6]). Let D be a strong digraph of order p ≥ 3. Suppose that
d(x) + d(y) ≥ 2p−2 for every pair of non-adjacent vertices x, y of V (D). Then D contains
a Hamiltonian bypass, unless D is isomorphic to a digraph of the set D0 ∪{Dp−k,k, T5, C3}.

The author [10] proved the following results.

Theorem 3: (Darbinyan [10]). For every integer p ≥ 8 there is a 2-strong non-Hamiltonian
digraph of order p, which has p− 1 vertices of degrees at least p.

Theorem 4: (Darbinyan [9]). Let D be a 2-strong digraph of order p ≥ 3 with the mini-
mum degree at least p−4. If p−1 vertices of D have degrees at least p, then D is Hamiltonian.

Theorem 5: (Darbinyan [10]). Let D be a strong digraph of order p ≥ 3. Suppose that
d(x) + d(y) ≥ 2p− 1 for every pair of non-adjacent vertices x, y ∈ V (D) \{z0}, where z0 is
some vertex in V (D). Then D contains a cycle of length at least p− 1.

The following corollary follows from Theorem 5.

Corollary 1: Let D be a strong digraph of order p ≥ 3. If p − 1 vertices of V (D) have
degrees at least p, then D is Hamiltonian or contains a cycle of length p− 1 (in fact, D has
a cycle that contains all the vertices with degrees at least p).

Remark 1: For the proof of Theorem 3, it suffices to consider a digraph H(n) of order
n ≥ 8, which is defined as follows:

V (H(n)) := {x0, x1, x2, . . . , xn−4, y1, y2, y3} and

A(H(n)) := {yiyj |i 6= j}∪{xixi+1 |0 ≤ i ≤ n− 4}∪{yixj |1 ≤ i ≤ 3, 1 ≤ j ≤ n− 6}

∪{xixj |1 ≤ j < i ≤ n− 4}∪{xn−4yi, xn−6 |1 ≤ i ≤ 3}∪{xixn−5 |1 ≤ i ≤ n− 7}

∪{x0xn−5, xn−5x0, xn−4x0, xn−6xn−4}.

Note that Theorem 3 disproves a conjecture of Thomassen ([2]. Every 3-strong digraph of
order p with minimum degree at least p + 1 is strongly Hamitonian-connected).

In this paper, we prove the following theorem.

Theorem 6: Let D be a 2-strong digraph of order p ≥ 3. Suppose that d(x) ≥ p for every
vertex x ∈ V (D)\{x0}, where x0 is a vertex of D. If D is Hamiltonian or d(x0) > 2(p−1)/5,
then D contains a Hamiltonian bypass.



S. Darbinyan 9

2. Terminology and Notation

In this paper, we consider finite digraphs without loops and multiple arcs. For a digraph D,
we denote by V (D) the vertex set of D and by A(D) the set of arcs in D. The order of D is the
number of its vertices. Let x, y be distinct vertices in D. The arc of a digraph D directed from
x to y is denoted by xy (we say that x dominates y). For disjoint subsets A and B of V (D) we
define A(A → B) as the set {xy ∈ E(D) |x ∈ A, y ∈ B}, A(A, B) = A(A → B)∪A(B → A).
The notation A → B denotes that every vertex of A dominates every vertex of B. A 7→ B
means that A → B and there is no arc from a vertex of B to a vertex of A. If x ∈ V (D) and
A = {x}, we write x instead of {x}. The out-neighborhood of a vertex x is the set N+(x) =
{y ∈ V (D) |xy ∈ A(D)} and N−(x) = {y ∈ V (D) |yx ∈ A(D)} is the in-neighborhood of
x. Similarly, if A ⊆ V (D), then N+(x, A) = {y ∈ A |xy ∈ A(D)} and N−(x, A) = {y ∈
A |yx ∈ A(D)}. The out-degree of x is d+(x) = |N+(x)| and d−(x) = |N−(x)| is the in-degree
of x. Similarly, d+(x, A) = |N+(x, A)| and d−(x, A) = |N−(x, A)|. The degree of the vertex
x in D is defined as d(x) = d+(x) + d−(x) (similarly, d(x, A) = d+(x, A) + d−(x, A)).

The subdigraph of D induced by a subset A of V (D) is denoted by D[A]. The path
(respectively, the cycle) consisting of the distinct vertices x1, x2, . . . , xm (m ≥ 2) and the
arcs xixi+1, 1 ≤ i ≤ m − 1 (respectively, xixi+1, 1 ≤ i ≤ m − 1, and xmx1), is denoted by
x1x2 · · ·xm (respectively, x1x2 · · ·xmx1). We say that x1x2 · · ·xm is a path from x1 to xm or
is an (x1, xm)-path. The length of a cycle or a path is the number of its arcs. A cycle of
length k, k ≥ 2, is denoted by Ck. For a cycle Ck := x1x2 · · ·xkx1, the subscripts considered
modulo k, i.e., xi = xs for every s and i such that i ≡ s (mod k). If P is a path containing a
subpath from x to y, we let P [x, y] denote that subpath. Similarly, if C is a cycle containing
vertices x and y, C[x, y] denotes the subpath of C from x to y. For a digraph D of order n,
by D(n, 2) = [x1xn; x1x2x3 . . . xn] we denote a Hamiltonian path in which the initial vertex
x1 dominates the terminal vertex xn.

A digraph D is strongly connected (or, just, strong) if there exists a path from x to y
and a path from y to x for every pair of distinct vertices x, y. A digraph D is k-strongly
connected (or, k-strong), if |V (D)| ≥ k + 1 and D[V (D) \ A] is strong for any set A of at
most k−1 vertices. Two distinct vertices x and y of a digraph D are adjacent if xy ∈ A(D)
or yx ∈ A(D) (or both). By K∗n is denoted the complete digraph of order n.

3. Preliminaries

The following well-known simple Lemmas 1-3 are the basis of our results and other theorems
on directed cycles and paths in digraphs. They will be used extensively in the proof of our
result.

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

The following lemma is a modification of a lemma by Bondy and Thomassen [13].

Lemma 2: Let D be a digraph of order p ≥ 3 containing a path P := x1x2 . . . xm, 2 ≤ m ≤
p− 1 and x be a vertex not contained in this path. If one of the following conditions holds:



10 A Note on Hamiltonian Bypasses in Digraphs with Large Degrees

(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, xx1 /∈ A(D) and xmx /∈ A(D);

then there is an i, 1 ≤ i ≤ m − 1, such that xix, xxi+1 ∈ A(D) i.e., x1x2 . . . xixxi+1 . . . xm
is a path of length m D (we say that x can be inserted into P ).

The following lemma is a simple extension of a lemma by Bang-Jensen, Gutin and Li [14].

Lemma 3: Let P = u1u2 . . . us be a path in a digraph D (possibly, s = 1) and let
Q = v1v2 . . . vt be a path (or Q = v1v2 . . . vtv1 be a cycle) in D[V (D)\V (Q)], t ≥ 2. Suppose
that for each ui, 1 ≤ i ≤ s, there is an arc vjvj+1 on Q such that vjui, uivj+1 ∈ A(D). Then
there is a (v1, vt)-path (or a cycle) of length t + k − 1 (respectively, t + k), 1 ≤ k ≤ s, with
vertex set {v1, v2, . . . , vt}∪{u1, u2, . . . , uk}.

4. Proofs of the Main Results

Theorem 6: Let D be a 2-strong digraph of order p ≥ 3. Suppose that d(x) ≥ p for every
vertex x ∈ V (D)\{x0}, where x0 is a vertex of D. If D is Hamiltonian or d(x0) > 2(p−1)/5,
then D contains a Hamiltonian bypass.

Proof: Suppose, on the contrary, that is D contains no Hamiltonian bypass. We first will
prove the following claim (note that in the proofs of Claim 1 and Case 1, we do not use the
fact that D is 2-strong).

Claim 1: D has no cycle of length l through x0, where l = p− 1 or l = p− 2.
Proof: Suppose that the claim is not true. Assume that Cp−1 = x1x2 . . .
xp−1x1, x0 ∈ V (Cp−1) and y /∈ V (Cp−1). Since D contains no Hamiltonian bypass, for every
i, 1 ≤ i ≤ p− 1, we have d+(y,{xi, xi+1}) ≤ 1 and d−(y,{xi, xi+1}) ≤ 1. Therefore,

2d(y) =
p−1∑
i=1

(d+(y,{xi, xi+1}) + d−(y,{xi, xi+1})) ≤ 2(p− 1),

which contradicts that d(y) ≥ p. Thus, D contains no cycle of length p− 1 through x0.
Now assume that D contains a cycle of length p− 2 through x0. Let Cp−2 = x1x2 . . .

xp−2x1, x0 ∈ V (Cp−2) and x, y /∈ V (Cp−2). Since D contains no cycle of length p − 1
through x0, from Lemma 1 it follows that xy, yx ∈ A(D), d(x, V (Cp−2)) = d(y, V (Cp−2)) =
p − 2 and there is a vertex xi such that the vertices x, xi are not adjacent and the arcs
xi−1x, xxi+1 are in D. If yxi ∈ A(D), then D(p, 2) = [yxi; yxC[xi+1, xi]], if xiy ∈ A(D),
then D(p, 2) = [xiy; C[xi, xi−1]xy], a contradiction. We may therefore assume that xi and
y also are not adjacent. Using this, Lemmas 1, 2 and the fact that D contains no cycle
of length p − 1 througt x0, we obtain that xi = x0, xi−1y, yxi+1 ∈ A(D) and the vertex x
(y) is adjacent to every vertex in V (D) \{x0}. Hence, we have that if xxi+2 ∈ A(D), then
D(p, 2) = [yxi+1; yxC[xi+2, xi+1]], a contradiction. If xxi+2 /∈ A(D), then xi−2x ∈ A(D) and
D(p, 2) = [xi−1y; C[xi−1, xi−2]xy], a contradiction. Claim 1 is proved.

Now, we divide the proof into two cases to consider.
Case 1. D is Hamiltonian.



S. Darbinyan 11

Let Cp = x1x2 . . . xpx1 be a Hamiltonian cycle in D. Since D contains no Hamiltonian
bypass, we have that xi+1xi /∈ A(D) for every i, 1 ≤ i ≤ p. Using this, it is not difficult to
check that if p ≤ 6, then D contains a Hamiltonian bypass. We may therefore assume that
p ≥ 7.
Claim 2: If x0 6= xi+1, then the vertices xi and xi+2 are not adjasent, where 1 ≤ i ≤ p.
Proof: Suppose, on the contrary, that is for some i, 1 ≤ i ≤ p, x0 6= xi+1 and the vertices
xi, xi+2 are adjasent. Without loss of generality we may assume that i = 1. Since x0 6= x2,
we have d(x2) ≥ p and, by Claim 1, x1x3 /∈ A(D). Hence, x3x1 ∈ A(D). It is clear that
x0 6= x1 or x0 6= x3. This together with Claim 1 implies that xpx2 /∈ A(D) or x2x4 /∈ A(D).
Since there is no (x3, x1)-Hamiltonian path, using Lemma 2(ii) , we obtain that

d(x2, V (D) \{x2}) = d(x2,{x1, x3}) + d(x2, V (D) \{x1, x2, x3}) ≤ 2 + p− 3 = p− 1,

which contradicts that d(x2) ≥ p.

It is not difficult to show that there are two distinct vertices xi and xi+k such that
xi+kxi ∈ A(D) and x0 /∈ {xi+1, xi+2, . . . , xi+k−1}. We may assume that k is chosen so that
k is the smallest possible. Without loss of generality we may assume that i = 1. Then
d−(x1,{x2, x3, . . . , xk}) = 0. From Claim 2 it follows that 3 ≤ k ≤ p− 2.

Assume first k = 3, i.e., x4x1 ∈ A(D). By Claim 2, the vertices x2 and x4 (x1 and x3)
are not adjacent since x0 /∈ {x2, x3}. Now from xi+1xi /∈ A(D), d(x2) ≥ p and d(x3) ≥ p it
follows that

d(x2,{x5, x6, . . . , xp}) ≥ p− 2 and d(x3,{x5, x6, . . . , xp}) ≥ p− 2.

Hence, by Lemma 2, the vertex x2 (x3) can be inserted into x5x6 . . . xp. Then, by Lemma 3,
there is an (x4, x1)-Hamiltonian path, which is a contradiction as x4x1 ∈ A(D).

Assume next that k ≥ 4. By Claim 2, the vertices xi and xi+2, where 1 ≤ i ≤ k − 1 are
not adjacent. From the minimality of k it follows that if 1 ≤ i < j ≤ k + 1, then xjxi ∈ A(D)
if and only if j = k + 1 and i = 1. From the minimality of k ≥ 4 and Claim 1 it follows that
for each xi ∈{x1, x2, . . . , xk−2},

d(xi,{xi+2, xi+3}) = d(xk−1,{xk+1}) = 0. (1)

Also we need to show the following claim.
Claim 3: Suppose that 1 ≤ i < j − 1 ≤ k. Then xixj ∈ A(D) if and only if i = 1 and
j = k + 1.
Proof: For a proof by contradiction, suppose that xmxn ∈ A(D), where 1 ≤ m < n−1 ≤ k
and m 6= 1 or n 6= k+1. Without loss of generality, we may assume that n−m is the minimum
possible. From (1) it follows that n−m ≥ 4, i.e., |{xm+1, . . . , xn−1}| = n−m−1 ≥ 3. Note
that R := xmxnxn+1 . . . xpx1x2 . . . xm is a cycle of length p−n + m + 1 ≤ p− 3 through x0.
By the minimality of k and n−m, for every y ∈{xm+1, . . . , xn−1} we have

d(y,{xm+1, . . . , xn−1}) ≤ 2 and d(y, V (R)) ≥ p− 2.

Therefore, by Lemma 1, every vertex y ∈ {xm+1, . . . , xn−1} can be inserted into R. Now
using Lemma 3, we obtain a cycle of length p− 1 through x0, which contradicts Claim 1.

From Claim 3 and the minimality of k ≥ 4 it follows that

d(x2,{x2, x3, . . . , xk}) = d(xk,{x2, x3, . . . , xk}) = 1



12 A Note on Hamiltonian Bypasses in Digraphs with Large Degrees

and for every i, 3 ≤ i ≤ k − 1, d(xi,{x2, x3, . . . , xk}) = 2. Therefore, d(xi, V (Q)) ≥ p − 2,
where 2 ≤ i ≤ k and Q := xk+1xk+2 . . . xpx1. Note that |V (Q)| = p − k + 1. If k ≥ 5, then
|V (Q)| ≤ p − 4, and, by Lemma 2(i), every vertex xi, 2 ≤ i ≤ k, can be inserted into Q. If
k = 4, then |V (Q)| = p−3, d(x2, V (Q)) ≥ p−1, d(x4, V (Q)) ≥ p−1 and d(x3, V (Q)) ≥ p−2.
Since d(x3,{x1, x5}) = 0, again using Lemma 2, we obtain that each vertex xi ∈{x2, x3, x4}
can be inserted into Q. Therefore, by Lemma 3, there is an (xk+1, x1)-Hamiltonian path,
which contradicts our initial supposition since xkx1 ∈ A(D). The discussion of Case 1 is
completed.

Case 2. D is not Hamiltonian.
(*) Observe that by Claime 1, in this case every cycle through x0 in D has length at

most p− 3.
Then, by Corollary 1, D contains a cycle of length p − 1. Let Cp−1 = x1x2 . . . xp−1x1 be

a cycle of length p − 1 in D. By Claim 1, x0 ∈ V (Cp−1). For this case, we first give the
following claim and lemma.
Claim 4: Let P := x1x2 . . . xp−1 be an (x1, xp−1)-path of length p−2 through x0 in D. Then
x1xp−1 /∈ A(D).
Proof: For a proof by contradiction, suppose that x1xp−1 ∈ A(D). Let x /∈ V (P ). Then
d(x) ≥ p since x 6= x0. Since D contains no Hamiltonian bypass, it follows that x cannot be
inserted into P . Now using Lemma 2(i) and d(x) ≥ p, we obtain that xp−1x and xx1 ∈ A(D).
Therefore, x1x2 . . . xp−1xx1 is a Hamiltonian cycle in D, which contradicts the hypothesis of
this case.
Lemma 4: D contains no cycle of length p− 3 through x0.
Proof: Suppose that the lemma is not true. Let C := x1x2 . . .
xp−4x0x1 be a cycle of length p − 3 through x0 in D and let B := V (D) \ V (C). By Claim
1, D contains no cycle of length p − 1 and p − 2 through x0. This together with Lemma 1
implies that for every y ∈ B,

p ≤ d(y) = d(y, V (C)) + d(y, B) ≤ p− 3 + d(y, B).

Therefore, d(y, B) ≥ 3. This implies that D[B] is Hamiltonian since |B| = 3, in particular,
D[B] is strong.

We now consider the folowing two cases.
Case (a). There exists a vertex y ∈ B, which is adjacent to every vertex xi for all i,

1 ≤ i ≤ p− 4.
Let yuzy be a Hamiltonian cycle in D[B].
If y and x0 are adjacent then using the observation (*), it is not difficult to show that

either d−(y, V (C)) = 0 or d+(y, V (C)) = 0. Without loss of generality, we assume that
d+(y, V (C)) = 0. Then V (C) 7→ y. This together with Claim 1 implies that A(B → V (C)) =
∅, which contradicts that D is 2-strong. We may therefore assume that y and x0 are not
adjacent. If x1y ∈ A(D), then {x1, x2, . . . , xp−4}→ y. Therefore, A(B → V (C) \{x1}) = ∅.
This means that D[V (D) \ {x1}] is not strong, i.e., D is not 2-strong, a contradiction.
Now assume that x1y /∈ A(D). Then yx1 ∈ A(D) since y and x1 are adjacent. Similarly,
xp−4y ∈ A(D). Then by the above observation (*), d(x0, B) = 0. Let xky ∈ A(D) with
2 ≤ k ≤ p− 4 and k be the minimum possible. It is not dificult to show that

{xk, xk+1, . . . , xp−4}→ y →{x1, x2, . . . , xk−1}.

Assume first that k ≤ p − 5. Then by Claim 1, d−(xp−4, B) = 0. If xp−4z ∈ A(D), then
D(p, 2) = [xp−4z; xp−4x0x1 . . . xp−5yuz], a contradiction. Therefore, xp−4z /∈ A(D). Thus,



S. Darbinyan 13

d(z,{x0, xp−4}) = 0 and d(z,{x1, x2, . . . , xp−5}) ≥ p−4. Again using Lemma 2(i) and (*), we
obtain that xp−5z ∈ A(D). Therefore, xp−4x0x1 . . . xp−5zy is a path of length p − 2 through
x0 and xp−4y ∈ A(D), which contradicts Claim 4.

Assume next that k = p− 4. Then y →{x1, x2, . . . , xp−5}. Hence, if p− 5 ≥ 2, then for
the converse digraph of D we have the considered former case. For 4 ≤ p ≤ 6, this completes
the discussion of Case (a).

Case (b). For every y ∈ B there exists a vertex xk with 1 ≤ k ≤ p− 4 such that y and
xk are not adjacent.

To complete the proof of Lemma 4 in this case, we first prove the following claims.
Claim 5: xk−1y /∈ A(D) or yxk+1 /∈ A(D).
Proof: Suppose, on the contrary, that xk−1y ∈ A(D) and yxk+1 ∈ A(D). Note that
d(xk) ≥ p since xk 6= x0. Using observation (*), we obtain that d(xk, B) = 0. Now consider
the cycle R := x0x1 . . . xk−1yxk+1 . . . xp−4x0 of length p − 3 through x0. By Claim 1, xk
cannot be inserted into R (for otherwise we obtain a cycle of length p − 2 througth x0).
Therefore by Lemma 1, p ≤ d(xk) = d(xk, B) + d(xk, V (R)) ≤ p− 3, a contradiction.
Claim 6: (i) If xk−1y ∈ A(D), then xk+1y /∈ A(D). (ii) If yxk−1 ∈ A(D), then yxk+1 /∈
A(D).
Proof: (i) Suppose that the claim is not true. Then {xk−1, xk+1} → y. By Claim 5,
yxk+1 /∈ A(D). Since y cannot be inserted into the path C[xk+1, xk−1] and yxk+1 /∈ A(D),
from Lemma 2(ii) it follows that d(y, V (C)) = p− 4.

Assume first that there is a vertex xs 6= xk such that y and xs also are not adjacent. Let
s be chosen so that |V (C[xk, xs])| is the minimum possible. Note that xs /∈{xk−1, xk+1}.

Write P1 := C[xk+1, xs−1] and P2 := C[xs+1, xk−1]. Then

p− 4 = d(y, V (C)) = d(y, V (P1) + d(y, V (P2) ≤ |V (P1)| + |V (P2)| + 1 = p− 4.

This implies that d(y, V (P1)) = |V (P1)| and d(y, V (P2)) = |V (P2)| + 1. Now using Lemma
2, we obtain xs−1y ∈ A(D) and yxs+1 ∈ A(D). By Claim 5, xs = x0 and d−(xk+1, B) =
d(xs, B) = 0. Rcall that zyuz is a Hamiltonian cycle in D[B]. If xkz ∈ A(D), then
D(p, 2) = [xkz; C[xk, xk−1]yuz], a contradiction. Therefore, z and xk are not adjacent. Now
using Lemma 2, d(z) ≥ p, d(z,{xk, xs}) = 0 and the fact that d+(z,{xk+1, xk+2}) = 0, we
obtain xk+1z ∈ A(D). Therefore, C[xk+1, xk−1]yuz is a path of length p− 2 thruogh x0 and
xk+1z ∈ A(D), which contradicts Claim 4.

Assume next that y is adjacent to every vertex of V (C) \ {xk}. Then by Claim 1,
V (C) \{xk} 7→ y since xk+1y ∈ A(D) and yxk+1 /∈ A(D). Again using observation (*), we
obtain that A(B → V (C)) = ∅, which contradicts that D is 2-strong. This completes the
proof of Claim 6(i).

For the proof of Claim 6(ii), it suffices to consider the converse digraph of D. Claim 6 is
proved.
Claim 7: If yxk−1 ∈ A(D), then xk+1y /∈ A(D).
Proof: For a proof by contradiction, suppose that yxk−1 ∈ A(D) and xk+1y ∈ A(D).
Claim 6 implies that xk−1y /∈ A(D) and yxk+1 /∈ A(D). Since y cannot be inserted into
C[xk+1, xk−1], using Lemma 2(iii), we obtain d(y, V (C[xk+1, xk−1]) ≤ p − 5, which contra-
dicts that d(y, V (C)) ≥ p− 4. Claim 7 is proved.

Claim 8: (i) The vertices y and xk+1 are adjacent; (ii) The vertices y and xk−1 are adjacent.
Proof: (i) Suppose that the claim is not true, i.e., d(y,{xk, xk+1}) = 0. Write Q :=



14 A Note on Hamiltonian Bypasses in Digraphs with Large Degrees

C[xk+2, xk−1]. Then d(y, V (Q)) = p − 4. Therefore by Lemma 2, yxk+2 ∈ A(D) and
xk−1y ∈ A(D) since y cannot be inserted into Q.

Assume first that xk+1 6= x0. We know that d(xk) ≥ p and d(xk+1) ≥ p. Using obveration
(*), it is not difficult to show that d(xk, B) = d(xk+1, B) = 0. Therefore, d(xk, V (Q)) ≥ p−2
and d(xk+1, V (Q)) ≥ p−2. These together with Lemmas 2 and 3 imply that the vertices xk
and xk+1 both can be inserted into Q. As a consequence, we obtain a cycle of length p − 2
through x0, which contradicts Claim 1.

Assume next that xk+1 = x0. Then d(x0, B) = d
−(xk, B) = 0. If xkz ∈ A(D), then

D(p, 2) = [xkz; C[xk, xk−1]yuz], a contradiction. If xku ∈ A(D), then C[xk, xk−1]yz is a path
of length p − 2 through x0 and xku ∈ A(D), which contradicts Claim 4. We may there-
fore assume that d(z,{xk, xk+1}) = d(u,{xk, xk+1}) = 0. Therefore, d(z, V (Q)) = p − 4,
zxk+2 and xk−1z ∈ A(D). Now using Claims 1 and 5, we obtain that there is a vertex xs
such that {y, z} → V (C[xk+2, xs]) and V (C[xs, xk−1]) → {y, z}. Whitout loss of generality,
assume that |V (C[xk+2, xs])| ≥ 2 (for otherwise we consider the converse digraph of D).
Then D(p, 2) = [yxk+2; yuzC[xk+3, xk+2]], a contradiction. This contradiction completes the
proof of Claime 8(i). By the same arguments one can prove Claim 8(ii). Claim 8 is proved.

Now we return to the proof of the lemma. From Claim 8 it follows that y is adjacent to
xk−1 and xk+1. Therefore, only the following cases are possible: (i) xk−1y and yxk+1y ∈ A(D),
(ii) {xk−1, xk+1} → y, (iii) y → {xk−1, xk+1}, (iv) xk+1y and yxk−1 ∈ A(D). On the other
hand, Claims 5, 6 and 7 imply that none of these cases holds. This contradiction completes
the discussion of Case (b). Lemma 4 is proved.

Now we are ready to complete the proof of the theorem in Case 2. Since D is not
Hamiltonian, by Corollary 1, D contains a cycle of length p−1. Let R := x1x2 . . . xp−1x1 be
a cycle of length p − 1 in D. Then by Claim 1 and Lemma 4, we know x0 /∈ V (R) and for
every i, j, 1 ≤ i, j ≤ p− 1 the following hold:

d−(x0,{xi}) + d+(x0,{xi+1, xi+2, xi+3, xi+4}) ≤ 1,

d+(x0,{xj}) + d−(x0,{xj−1, xj−2, xj−3, xj−4}) ≤ 1.

Therefore, d−(x0) + 4d
+(x0) ≤ p − 1 and 4d−(x0) + d+(x0) ≤ p − 1. These mean that

5d(x0) ≤ 2p − 2, i.e., d(x0) ≤ 2(p − 1)/5, which contradicts that d(x0) > 2(p − 1)/5. The
theorem is proved.

Corollary 2: (Benhocine [5]). Every strong digraph D of order p ≥ 3 and with minimum
degree at least p contains D(p, 2).

Proof: By the famous theorem of Ghoula-Houri, D is Hamiltonian. Therefore, from the
proof of Theorem 6 in Case (a), it follows that D contains a Hamiltonian bypass.

Perhaps the following proposition will be useful for Conjecture 1 (see, in section Conclu-
sion).

Proposition 1: Let D be a non-Hamiltonian 2-strong digraph of order p ≥ 3. Suppose that
d(x) ≥ p for every vertex x ∈ V (D) \{x0}, where x0 is a vertex of D. If P = x1x2 . . . xp−2
is an (x1, xp−2)-path of length p− 3 through x0 in D, then x1xp−2 /∈ A(D).



S. Darbinyan 15

Proof: For a proof by contradiction, suppose that x1xp−2 ∈ A(D). Write V (D) \ V (P ) =
{y1, y2}. We know that d(y1) ≥ p and d(y2) ≥ p since x0 ∈ V (P ). From Claim 4 it
follows that yi cannot be inserted into P . On the other hand, since D contains no cycle
of length p − 1 through x0, we have that yix1 /∈ A(D) or xp−2yi /∈ A(D). Now using
Lemma 2(ii), we obtain d(yi, V (P )) = p − 2 and y1y2, y2y1 ∈ A(D). Without loss of
generality, assume that y1x1 /∈ A(D). Then by Lemma 2(ii), xp−2y1 ∈ A(D). Since D is not
Hamiltonian and contains no cycle of length p−1 through x0, it follows that d−(x1,{y1, y2}) =
0. Then xp−2y2 ∈ A(D). If x1y1 ∈ A(D) (or x1y2 ∈ A(D)), then it is not difficult to show
that D(p, 2) = [x1y1; x1x2 . . . xp−2y2y1] (or D(p, 2) = [x1y2; x1x2 . . . xp−2y1y2]) is in D, a
contradiction. Therefore, d+(x1,{y1, y2}) = 0. Thus, d(x1,{y1, y2}) = 0. This together with
Lemma 2 and d(yi, V (P )) = p − 2 implies that {y1, y2} → x2. Then by Claim 1, x1 = x0
since x2x3 . . . xp−2y1y2x2 is a cycle of length p− 1.

Write Q := x2x3 . . . xp−2. Then |V (Q)| = p − 3, d(y1, V (Q)) ≥ p − 2 and d(y2, V (Q)) ≥
p−2. Since x0 →{x2, xp−2}, by Claim 4 we have that neither y1 nor y2 can be inserted into
Q. Then by Lemma 2(iii), we obtain that d(y1, V (Q)) = d(y2, V (Q)) = p − 2 and the arcs
y2y1, xp−2y2, y1x2 are in A(D).

We claim that the vertex y1 (y2) is adjacent to each vertex of V (Q).
Assume that this is not the case. Let d(y1,{xi}) = 0, where 3 ≤ i ≤ p−3. From Lemma

2(iii), d(y1, V (Q)) = p−2 and the fact that the vertex y1 cannot be inserted into Q it follows
that xi−1y1, y1xi+1 ∈ A(D). Since y2y1, y1y2 ∈ A(D), it is easy to see that d(y2,{xi}) = 0
and xi−1y2, y2xi+1 ∈ A(D). They imply that the vertex xi can be inserted neither into
S := x2 . . . xi−1 nor into T := xi+1 . . . xp−2. Then it is easy to see that d(xi,{x0}) = 2 and

p− 2 ≤ d(xi, V (S)) + d(xi, V (T )) ≤ |V (S)| + |V (T )| + 2 = p− 2.

Therefore, d(xi, V (S)) = |V (S)| + 1 and d(xi, V (T )) = |V (T )| + 1. Again using Lemma 2,
we obtain xp−2xi and xix2 ∈ A(D). Hence, x0xix2 . . . xi−1y1y2xi+1 . . . xp−2 is an (x0, xp−2)-
Hamiltonian path, a contradiction as x0xp−2 ∈ A(D). This proves that y1 (y2) is adjacent
to every vertex in V (Q). Therefore, there is an integer l, 2 ≤ l ≤ p− 2, such that

{xl, xl+1, . . . , xp−2}→{y1, y2}→{x2, x3, . . . , xl}. (2)

If 3 ≤ l ≤ p− 3, then by (2), x0xp−2y1x3 . . . xp−3y2x2 is an (x0, x2)-Hamiltonian path, which
is a contradiction as x0x2 ∈ A(D). If l = 2 or l = p−2, then A({y1, y2}→ V (D)\{x2}) = ∅
or A(V (D) \{xp−2}→{y1, y2}) = ∅ when l = 2 or l = p− 2, respectively. This means that
D is not 2-strong, a contradiction. Proposition 1 is proved.

5. Conclusion

In the current article, we examined the existence of a Hamiltonian bypass in 2-strong digraphs
of order p, in which p−1 vertices have degrees at least p. We proved that if such digraphs are
Hamiltohian or have the minimal degree more than 2(p − 1)/5, then such digraphs contain
a Hamiltonian bypass.

If we consider the digraph H(n) (by Remark 1, H(n) is 2-strong, d(x0) = 4 and is not
Hamiltonian), then we see that D(n, 2) = [y1x1; y1y2y3x2x3 . . . xn−4x0x1] is a Hamiltonian
bypass. By the above arguments, we believe that the following conjecture is true.
Conjecture 1: Let D be a 2-strong digraph of order p. If p − 1 vertices in V (D) have
degrees at least p, then D contains a Hamiltonian bypass.



16 A Note on Hamiltonian Bypasses in Digraphs with Large Degrees

Acknowledgements

The author would like to thank the referees of the paper for careful reading and many helpful
remarks.

References

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

[2] J.-C. Bermond and C. Thomassen, “Cycles in Digraphs-A Survey”, Journal of Graph
Theory, vol. 5, 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. Benhocine and A.P. Wojda, “Bypasses in Digraphs”, Ars Combinatoria, vol. 16, pp.
85-94, 1983.

[5] A. Benhocine, “On the existence of a specified cycle in digraphs with constraints on
degrees”, Journal of Graph Theory, vol. 8, pp. 101-107, 1984.

[6] S.Kh. Darbinyan, “On Hamiltonian bypasses in digraphs satisfying Meyniel-like condi-
tion”, Transactions of IIAP of NAS RA, Mathematical Problems of Computer Science,
vol. 20, pp. 7-19, 1998.

[7] S.Kh. Darbinyan, “On the specified cycles in oriented graphs”, Akademy Nauk Armyan.
SSR Dokllady, vol. 84, no. 2, pp. 51-55, 1987 (in Russian).

[8] S.Kh. Darbinyan and I.A. Karapetyan, “On Hamiltonian bypasses in one class of Hamil-
tonian digraphs”, Mathematical Problems of Computer Science, vol. 41, pp. 23-37, 2014.

[9] S.Kh. Darbinyan, “On Hamiltonian bypasses in digraphs with the condition of Y.
Manoussakis”, ”2015 Computer Science and Information Technologies (CSIT), Yere-
van, doi:10.1109/CSITechnol.2015.7358250, pp. 53-63, 2015.

[10] S.Kh. Darbinyan, “On Hmiltonian and strongly Hamilton-
connected digraphs”, Akademy Nauk Armyan. SSR Doklady, vol. 91, no. 1, pp. 3-6,
1990.(arXiv.1801.05166v1).

[11] S.Kh. Darbinyan, “A sufficient condition for a digraph to be Hamiltonian”, Akademy
Nauk Armyan. SSR Doklady,(in Russian), vol. 91, no. 2, pp. 57-59, 1990.

[12] R. Häggkvist and C. Thomassen, “On pancyclic digraphs”, Journal Combinatorial The-
ory ser. B, vol. 20, pp. 20-40, 1976.

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

[14] J. Bang-Jensen, G. Gutin and H. Li, “Sufficient conditions for a digraph to be Hamil-
tonian”, Journal of Graph Theory, vol. 22, no. 2, pp. 181-187, 1996.

Submitted 03.08.2020, accepted 01.12.2020.



S. Darbinyan 1 7

Ø»Ï Ýϳï³éáõÙ Ù»Í ³ëïÇ׳ÝÝ»ñáí ÏáÕÙÝáñáßí³Í ·ñ³ýÝ»ñáõÙ

ѳÙÇÉïáÝÛ³Ý ßñç³ÝóáõÙÝ»ñÇ Ù³ëÇÝ

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

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

e-mail: samdarbin@iiap.sci.am

²Ù÷á÷áõÙ

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

p ¡ 1 ·³·³ÃÝ»ñÇ ³ëïÇ׳ÝÝ»ñÁ ÷áùñ ã»Ý p ÃíÇó: ºÃ» D -Ý Ñ³ÙÇÉïáÝÛ³Ý ¿ ϳÙ
D-Ç ÷áùñ³·áõÛÝ ³ëïÇ׳ÝÁ Ù»Í ¿ 2 ( p ¡ 1 ) = 5 ÃíÇó, ³å³ ³Û¹ ·ñ³ýÁ å³ñáõݳÏáõÙ ¿

ßñç³ÝóáõÙ:

Îäíà çàìåòêà î ãàìèëüòîíîâûõ îáõîäàõ â îðãðàôàõ
ñ áîëüøèìè ñòåïåíüÿìè

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

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

Àííîòàöèÿ

 íàñòîÿùåé ðàáîòå äîêàçàíà ñëåäóþùàÿ òåîðåìà:
Òåîðåìà: Ïóñòü D åñòü 2-ñèëüíî ñâÿçíûé p-âåðøèííûé îðãðàô, â êîòîðîì

p ¡ 1 âåðøèíû èìåþò ñòåïåíü íå ìåíüøå ÷åì p. Åñëè D ãàìèëüòîíîâ èëè èìååò
ìèíèìàëüíóþ ñòåïåíü áîëüøå ÷åì 2 ( p ¡ 1 ) =5 , òî D ñîäåðæèò ãàìèëüòîíîâ îáõîä.

Êëþ÷åâûå ñëîâà: Îðãðàô, öèêë, ãàìèëüòîíîâ öèêë, ãàìèëüòîíîâ îáõîä.

ѳÙÇÉïáÝÛ³Ý ßñç³ÝóáõÙ:
´³Ý³ÉÇ µ³é»ñ` ÎáÕÙÝáñáßí³Í ·ñ³ý, óÇÏÉ, ѳÙÇÉïáÝÛ³Ý óÇÏÉ, ѳÙÇÉïáÝÛ³Ý


	01_Darbinyan_54_7_17
	SamvelDarbinyan