Mathematical Problems of Computer Science 51, 21–38, 2019. UDC 519.1 On the Manoussakis Conjecture for a Digraph to be Hamiltonian Samvel Kh. Darbinyan Institute for Informatics and Automation Problems of NAS RA e-mail: samdarbin@ipia.sci.am Abstract Y. Manoussakis (J. Graph Theory 16, 1992, 51-59) proposed the following conjec- ture. Conjecture. Let D be a 2-strongly connected digraph of order n such that for all distinct pairs of non-adjacent vertices x, y and w, z, we have d(x)+d(y)+d(w)+d(z) ≥ 4n − 3. Then D is Hamiltonian. In this note, we prove that if D satisfies the conditions of this conjecture, then (i) D has a cycle factor; (ii) If {x, y} is a pair of non-adjacent vertices of D such that d(x) + d(y) ≤ 2n − 2, then D is Hamiltonian if and only if D contains a cycle passing through x and y; (iii) If {x, y} a pair of non-adjacent vertices of D such that d(x)+d(y) ≤ 2n−4, then D contains cycles of all lengths 3, 4, . . . , n−1; (iv) D contains a cycle of length at least n − 1. Keywords: Digraph, Hamiltonian cycle, Cycle factor, Pancyclic digraph. 1. Introduction In this paper, we consider finite digraphs (directed graphs) without loops and multiple arcs. Every cycle and path are assumed simple and directed. A digraph D is Hamiltonian if it contains a cycle passing through all the vertices of D. There are many conditions that guar- antee that a digraph is Hamiltonian (see, e. g., [1]-[5]). In [5], the following theorem was proved. Theorem 1.1: (Manoussakis [5]). Let D be a strongly connected digraph of order n. Suppose that D satisfies the following condition for every triple x, y, z ∈ V (D) such that x and y are non-adjacent: If there is no arc from x to z, then d(x) + d(y) + d+(x) + d−(z) ≥ 3n − 2. If there is no arc from z to x, then d(x)+d(y)+d−(x)+d+(z) ≥ 3n−2. Then D is Hamiltonian. Definition 1.2: Let D be a digraph of order n. We say that D satisfies condition (M ) when d(x) + d(y) + d(w) + d(z) ≥ 4n−3 for all distinct pairs of non-adjacent vertices x, y and w, z. 21 22 On the Manoussakis Conjecture for a Digraph to be Hamiltonian Manoussakis [5] proposed the following conjecture. This conjecture is an extension of Theorem 1.1 Conjecture 1.3: (Manoussakis [5]). Let G be a 2-strongly connected digraph of or- der n such that for all distinct pairs of non-adjacent vertices x, y and w, z we have d(x) + d(y) + d(w) + d(z) ≥ 4n − 3. Then D is Hamiltonian. This conjecture seems quite difficult to prove. Manoussakis [5] gave an example, which showed that if the conjecture is true, then the minimum degree condition is sharp. Notice that another examples can be found in [6], where for any two integers k ≥ 2 and m ≥ 1, the author constructed a family of k-strongly connected digraphs of order 4k + m with minimum degree 4k + m − 1, which are not Hamiltonian. This result improves a conjecture of Thomassen [2] (Conjecture 1.4.1). Moreover, when m = 1, then from these digraphs we can obtain k-strongly connected non-Hamiltonian digraphs of order n = 4k + 1 with minimum degree equal to n−1 and the minimal semi-degrees equal to (n−3)/2. Thus, if in Conjecture 1.3 we replace 4n−4 instead of 4n−3, then for every n there are many digraphs of order n with high connection and high semi-degrees, for which Conjecture 1.3 is not true. The author [7] proved the following theorem. Theorem 1.4: (Darbinyan [7]). Let D be a strongly connected digraph of order n ≥ 3. Suppose that d(x) + d(y) ≥ 2n − 1 for every pair of non-adjacent vertices x, y ∈ V (D) \{z}, where z is some vertex of V (D). Then either D is Hamiltonian or contains a cycle of length n − 1. It is easy to see that if a digraph D satisfies the condition (M ), then it contains at most one pair of non-adjacent vertices x, y such that d(x) + d(y) ≤ 2n−2. From this and Theorem 1.4 immediately follows the following corollary. Corollary 1.5: Let G be a strongly connected digraph of order n satisfying condition (M ). Then D contains a cycle of length at least n − 1 (in particular, D contains a Hamiltonian path). Corollary 1.5 was also later proved by Ning [8]. In this paper we investigate the properties those digraphs, which satisfy the condition of Conjecture 1.3. Let D be a 2-strongly connected digraph of order n satisfying the condition (M ) and let {x, y} be a pair of non-adjacent vertices of D. In Section 4 we prove: (i) D has a cycle factor; (ii) If d(x) + d(y) ≤ 2n − 2, then D is Hamiltonian if and only if D contains a cycle passing through x and y; (iii) If d(x) + d(y) ≤ 2n − 4, then D contains cycles of all lengths 3, 4, . . . , n − 1; (iv) Suppose that x1x2 . . . xn−2yx1 is a cycle of length n−1 passing through y and avoiding x. If d(x) + d(y) ≤ 2n − 2 and xn−2 → x → x1, then D is Hamiltonian. S. Darbinyan 23 2. Terminology and Notation In this paper we consider finite digraphs without loops and multiple arcs. We shall assume that the reader is familiar with the standard terminology on digraphs and refer to [1] for terminology and notations not discussed here. The vertex set and the arc set of a digraph D are denoted by V (D) and A(D), respectively. The order of D is the number of its vertices. For any x, y ∈ V (D), we also write x → y if xy ∈ A(D). If xy ∈ A(D), y is an out-neighbour of x and x is an in-neighbour of y. If x → y and y → z, we write x → y → z. Two distinct vertices x and y are adjacent if xy ∈ A(D) or yx ∈ A(D) (or both). If there is no arc from x to y, we shall use the notation xy /∈ A(D). We let N +(x), N−(x) denote the set of out-neighbours, respectively the set of in- neighbours of a vertex x in a digraph D. If A ⊆ V (D), then N +(x, A) = A ∩ N +(x) and N−(x, A) = A ∩ N−(x). 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〉. If z is a vertex of a digraph D, then the subdigraph D〈V (D) \ {z}〉 is denoted by D − z. For integers a and b, a ≤ b, let [a, b] denote the set of all integers, which are not less than a and are not greater than b. 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 path is the number of its arcs. We say that x1x2 · · · xm is a path from x1 to xm or is an (x1, xm)-path. Let x and y be two distinct vertices of a digraph D. Cycle that passing through x and y in D, we denote by C(x, y). A cycle (respectively, a path) that contains all the vertices of D, is a Hamiltonian cycle (respectively, is a Hamiltonian path). A digraph is Hamiltonian if it contains a Hamiltonian cycle. A digraph D of order n ≥ 3 is pancyclic if it contains cycles of all lengths m, 3 ≤ m ≤ n. For a cycle C = x1x2 · · · xkx1 of length k, 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. A digraph D is strongly connected, 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 (k ≥ 1) connected if |V (D)| ≥ k + 1 and D〈V (D) \ A〉 is strongly connected for any subset A ⊂ V (D) of at most k − 1 vertices. Let H be a non-trivial proper subdigraph of a digraph D. For the subdigraph H, a H- bypass is a path of length at least two with both end-vertices in H and no other vertices in H. If C is a non-Hamiltonian cycle in D and (x, y)-path P is a C-bypass with V (P ) ∩ V (C) = {x, y}, then we call the length of the path C[x, y] the gap of P with respect to C. A cycle factor in D is a collection of vertex disjoint cycles C1, . . . , Cl such that V (C1) ∪ . . . ∪ V (Cl) = V (D). For a pair of disjoint subsets A and B of V (D), we define A(A → B) = {xy ∈ A(D)|x ∈ A, y ∈ B} and A(A, B) = A(A → B) ∪ A(B → A). 24 On the Manoussakis Conjecture for a Digraph to be Hamiltonian 3. Preliminaries Lemma 3.1: (Häggkvist, Thomassen [9]). Let D be a digraph of ordere n ≥ 3 containing a cycle C of length m, m ∈ [2, n − 1]. Let x be a vertex not contained in this cycle. If d(x, V (C)) ≥ m + 1, then D contains a cycle of length k for all k ∈ [2, m + 1]. The following lemma is a modification of a lemma by Bondy and Thomassen [10], its proof is almost the same. Lemma 3.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 statements 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, xx1 /∈ A(D) and xmx /∈ A(D); then there is an i ∈ [1, m − 1] such that xix, xxi+1 ∈ A(D), i.e., D contains a path x1x2 . . . xixxi+1 . . . xm of length m (we say that x can be inserted into P or the path x1x2 . . . xixxi+1 . . . xm is an extended path obtained from P with x). It is not difficult to prove the following lemma. Lemma 3.3: Let D be a digraph of order n. Assume that xy /∈ A(D) and the vertices x, y in D satisfy the degree condition d+(x) + d−(y) ≥ n − 2 + k, where k ≥ 1. Then D contains at least k internally disjoint (x, y)-paths of length two. Lemma 3.4: (Bypass Lemma, Bondy [11]). Let D be a strongly connected non-separable (i.e., U G(D) is 2-connected) digraph and let H be a non-trivial proper subdigraph of D. Then D contains a H-bypass. Theorem 3.4: (Yeo [12]). Let D be a digraph. Then D has a cycle factor if and only if V (D) cannot be partitioned into subsets Y , Z, R1, R2 such that A(Y → R1) = A(R2 → R1∪Y ) = ∅, |Y | > |Z| and Y is an independent set. Theorem 3.5: (Meyniel [4]). Let D be a strongly connected digraph of order n ≥ 2. If d(x) + d(y) ≥ 2n − 1 for all pairs of non-adjacent vertices in D, then D is Hamiltonian. Before stating the main result of [14], we need to define a family of digraphs. Definition 3.6: For any integers n and m, (n + 1)/2 < m ≤ n − 1, let Φmn denote the set of digraphs D, which satisfy the following conditions: (i) V (D) = {x1, x2, . . . , xn}; (ii) xnxn−1 . . . x2x1xn is a Hamiltonian cycle in D; (iii) for each k, 1 ≤ k ≤ n − m + 1, the vertices xk and xk+m−1 are not adjacent; (iv) xjxi /∈ A(D) whenever 2 ≤ i + 1 < j ≤ n and (v) the sum of degrees for any two distinct non-adjacent vertices at least 2n − 1. Theorem 3.7: (Darbinyan [13], [14]). Let D be a strongly connected digraph of order n ≥ 3. Suppose that d(x) + d(y) ≥ 2n − 1 for all pairs of distinct non-adjacent vertices x, y in D. Then either (a) D is pancyclic or (b) n is even and D is isomorphic to one of K∗n/2,n/2, S. Darbinyan 25 K∗n/2,n/2 \ {e}, where e is an arbitrary arc of K∗n/2,n/2, or (c) D ∈ Φmn (in this case D does not contain a cycle of length m). Later on, Theorem 3.7 was also proved by Benhocine [15]. 4. Proofs of the Results From the definition of condition (M ) the following lemma follows. Lemma 4.1: Let D be a digraph of order n satisfying condition (M ). Then D contains at most one pair of non-adjacent vertices x, y such that d(x) + d(y) ≤ 2n − 2. Theorem 4.2: Let D be a 2-strongly connected digraph of order n ≥ 3 satisfying condition (M ). Suppose that {x, y} is a pair of non-adjacent vertices of D such that d(x) + d(y) ≤ 2n−2. Then D is Hamiltonian if and only if D contains a cycle passing through the vertices x and y. Proof. If D is Hamiltonian, then obviously it contain a cycle passing through x and y. Suppose that D contains a cycle passing through the vertices x and y but D is not Hamil- tonian. Let C be a longest cycle, say of length m, passing through x and y. Since D is not Hamiltonian, we have that m ≤ n − 1. From 2-connectednees of D and Bypass- Lemma it follows that there is a C-bypass, say P = uy1y2 . . . ykv, where u, v ∈ V (C) and y1, y2, . . . , yk ∈ V (D) \ V (C). Without loss of generality, assume that the gap |C[u, v]| − 1 of P is the minimum among the gaps of all C-bypasses. Then A(V (C[u, v]) \ {u, v}, V (P [y1, yk])) = ∅. (1) Put f := |V (C[u, v]) \{u, v}|. Since C is a longest cycle passing through x and y, it follows that f ≥ 1. Now we extend the path C[v, u] with the vertices of V (C[u, v]) \{u, v} as mach as possible. We obtain a (v, u)-path, say R. Then, since C is a longest cycle passing through x and y, R does not contain some vertices u1, u2, . . . , ud of V (C[u, v])\{u, v}. Using (1) and Lemma 3.2(i), for all yj and ui we obtain d(yj, V (C)) ≤ m−f + 1 and d(ui, V (C)) = d(ui, V (R)) + d(ui, {u1, . . . , ud}) ≤ m + d−1. By the minimality of the gap f + 1 we also have that D contains no path of the form yjzui and uizyj, where z ∈ B := V (D) \ (V (C) ∪ {y1, . . . , yk}). Therefore, d(ui, B) + d(yj, B) ≤ 2|B|. Now by a simple calculation we obtain d(ui)+d(yj) = d(ui, V (C))+d(yj, V (C))+d(ui, B)+d(yj, B)+d(ui, P [y1, yk])+d(yj, P [y1, yk]) ≤ m + d − 1 + m − f + 1 + 2|B| + 2k − 2 ≤ 2n − 2, a contradiction with Lemma 4.1 since ui and yj are not adjacent and {ui, yj} 6= {x, y}. Theorem 4.2 is proved. 26 On the Manoussakis Conjecture for a Digraph to be Hamiltonian Clearly, the existence of a cycle factor is a necessary condition for a digraph to be Hamil- tonian. Theorem 4.3: Let D be a 2-strongly connected digraph of order n satisfying condition (M ). Then D has a cycle factor. Proof. Suppose, on the contrary, that D has no cycle factor. By the Yeo theorem, V (D) can be partitioned into subsets Y , Z, R1, R2 such that A(Y → R1) = A(R2 → R1 ∪ Y ) = ∅, |Y | > |Z| and Y is an independent set. Using these and 2-connectedness of D, we obtain that it follows that |Z| ≥ 2 and hence, |Y | ≥ 3. Let x, y, z be three distinct vertices of Y . Since Y is an independent set, we have that {x, y} and {x, z} are two distinct pairs of non-adjacent vertices of V (D). Now using condition (M ), we obtain 4n−3 ≤ 2d(x) + d(y) + d(z) ≤ 8|Z|+ 4|R1|+ 4|R2|+ 4|Y |−4|Y | = 4n−4(|Y |−|Z|) ≤ 4n−4, a contradiction. Theorem 4.3 is proved. Using Yeo’s theorem, it is not difficult to show that in Theorem 4.3 the minimum degree condition is sharp. Theorem 4.4: Let D be a 2-strongly connected digraph of order n ≥ 3. Suppose that D contains at most one pair of non-adjacent vertices. Then D is Hamiltonian. Proof. Suppose, on the contrary, that D is not Hamiltonian. Therefore, D is not semicom- plete and contains exactly one pair, say {x, y}, of non-adjacent vertices. Then d(x) ≥ n − 2, d(y) ≥ n − 2 and d(z) ≥ n − 1 for all z ∈ V (D) −{x, y}. Since D is 2-strongly connected, it follows that both subdigraphs D − x and D − y both are strongly connected semicomplete digraphs. Therefore, D − x and D − y both are Hamiltonian. Let Cn−1 := x1x2 . . . xn−2yx1 be a Hamiltonian cycle in D − x. Since D is not Hamiltonian, from d(x) ≥ n − 2 and the fact that x is adjacent to every vertex of V (D) − {y} it follows that there exists an integer l ∈ [2, n − 3] such that {xl+1, xl+2, . . . , xn−2} → x → {x1, x2, . . . , xl}. (2) Similarly, for some k ∈ [2, n − 3] we have {xk+1, xk+2, . . . , xn−2} → y → {x1, x2, . . . , xk}. (3) Observe that for every pair of integers i, j, 1 ≤ i < j ≤ n − 2, in D there is no path of the types xi → y → xj and xi → z → xj. By symmetry between x and y, we may assume that k ≥ l. Then by (2), (3) and our observation we have A({x, y} → {xk+1, xk+2, . . . , xn−2}) = ∅ and {xk+1, xk+2, . . . , xn−2} → {x, y}. (4) From (4) and 2-connectedness of D it follows that there exist i ∈ [1, k−1] and j ∈ [k+1, n−2] such that xi → xj (for otherwise, A({x1, x2, . . . , xk−1, x, y} → {xk+1, xk+2, . . . , xn−2}) = ∅, which means that D − xk is not strongly connected). Note that y → xi+1. We choose j maximal with these properties. Using (2) and (3), it is easy to see that if xj−1 → x, then x1 . . . xixj . . . xn−2yxi+1 . . . xj−1xx1 is a Hamiltonian cycle, which contradicts our sup- position. We may therefore assume that xj−1x /∈ A(D). Then from k ≥ l, (4) and S. Darbinyan 27 the maximality of j it follows that j = k + 1 and xkx /∈ A(D). Hence, l = k and A({x1, x2, . . . , xk−1} → {xk+2, xk+3, . . . , xn−2}) = ∅. This together with (4) and 2- connectedness of D implies that there is an integer s ∈ [k + 2, n − 2] such that xk → xs. Therefore, x1 . . . xixk+1 . . . xs−1xxi+1 . . . xkxs . . . xn−2yx1 is a Hamiltonian cycle, a contradic- tion. Theorem 4.4 is proved. Remark: There is a strongly connected non-Hamiltonian digraph of order n ≥ 5, which is not 2-strongly connected and has exactly one pair of non-adjacent vertices. To see this, consider the following digraph D defined as follows: V (D) = {x1, x2, . . . , xn−2, y, z}, x1x2, . . . xn−2yx1 is a cycle of length n − 1 in D, N−(y) = N−(z) = {xk, xk+1, . . . , xn−2} and N +(y) = N +(z) = {x1, x2, . . . , xk}, where k ∈ [2, n − 3], D also contains all the arcs xjxi whenever 1 ≤ i < j ≤ n − 2 and it contain no other arcs. It is not difficult to check that D is neither 2-strongly connected nor Hamiltonian. Lemma 4.5: Let D be a 2-strongly connected digraph of order n ≥ 3 and let u, v be two distinct vertices in D. If D contains no cycle passing through u and v, then u, v are not adjacent and there is no path of length two between them. In particular, d+(u) + d−(v) ≤ n − 2, d−(u) + d+(v) ≤ n − 2 and d(u) + d(v) ≤ 2n − 4. Proof. It is obvious that u, v are not adjacent. Suppose, on the contrary, that in D there is a path of length two between the vertices u and v, say u → z → v or v → z → u. Since D is 2-strongly connected, it follows that D−z is strongly connected. Therefore, in D−z there is an (u, v)- and a (v, u)-path. It is easy to see that this (u, v)-path ((v, u)-path, respectively) together with v → z → u (u → z → v, respectively) forms a cycle passing through u and v. In both cases we have a contradiction, which proves that there is no path of length two between u and v. Therefore, by Lemma 3.3, d+(u)+d−(v) ≤ n−2 and d−(u)+d+(v) ≤ n−2. These imply that d(u) + d(v) ≤ 2n − 4. Lemma 4.5 is proved. Theorem 4.6: Let D be a 2-strongly connected digraph of order n ≥ 3 satisfying condition (M ). Suppose that {u, v} is a pair of non-adjacent vertices in D such that d(u) + d(v) ≤ 2n − 2. Then D is Hamiltonian or D contains a cycle of length n − 1 passing through u and avoiding v (passing through v and avoiding u). Proof. Suppose that D is not Hamiltonian. From Theorem 4.2 it follows that D contains no cycle passing through u and v. Therefore, by Lemma 4.5, d(u) + d(v) ≤ 2n − 4. Since D is 2-strongly connected, it follows that D − u and D − v both are strongly connected. From the last inequality and condition (M ) it follows that if {x, y} is a pair of non-adjacent vertices in D − u (in D − v, respectively), then the following inequalities holds: d(x, V (D) \ {u}) + d(y, V (D) \ {u}) ≥ 2(n − 1) − 1, (d(x, V (D) \ {v}) + d(y, V (D) \ {v}) ≥ 2(n − 1) − 1, respectively). Therefore, since D − u and D − v both are strongly connected, by Meyniel’s theorem D − u and D − v both are Hamiltonian, i.e., D contains a cycle of length n − 1 passing through u 28 On the Manoussakis Conjecture for a Digraph to be Hamiltonian and avoiding v (passing through v and avoiding u). Theorem 4.6 is proved. As an immediate corollary of Theorems 4.2 and 4.6 (respectively, Theorem 4.6 and Corol- lary 3.1), we obtain Corollary 4.7 (respectively, Corollary 4.8). Corollary 4.7: Let D be a 2-strongly connected non-Hamiltonian digraph of order n ≥ 3 sat- isfying condition (M ). Suppose that {u, v} is a pair of non-adjacent vertices in D such that d(u)+d(v) ≤ 2n−2. Then D contains at most one cycle of length two passing through u (v). Corollary 4.8: Let D be a 2-strongly connected non-Hamiltonian digraph of order n ≥ 3 satisfying condition (M ). Suppose that {u, v} is a pair of non-adjacent vertices in D such that d(u) + d(v) ≤ 2n − 2. Then d(u) ≤ n − 1 and d(v) ≤ n − 1 . Theorem 4.9: Let D be a 2-strongly connected digraph of order n ≥ 6 satisfying condition (M ). Suppose that {x, y} is a pair of non-adjacent vertices in D such that d(x) + d(y) ≤ 2n − 4. Then D contains cycles of all lengths 3, 4, . . . , n − 1. Proof. Suppose first that D contains exactly one pair of non-adjacent vertices, namely {x, y}. Then D − x is a strongly connected semicomplete digraph. Therefore, by the well- known theorem of Moser [16], D − x contains cycles of all lengths 3, 4, . . . , n − 1. Suppose next that D contains at least two distinct pairs of non-adjacent vertices. Let {u, v} be an arbitrary pair of non-adjacent vertices in V (D) \{x} (or in V (D) \{y}). From condition (M ) it follows that d(u) + d(v) ≥ 2n + 1. (5) Now we consider the subdigraph H := D −x. For the digraph H we first prove the following claim. Claim: If H ∼= K∗m,m − e, where e is an arbitrary arc of K∗m,m, then D contains cycles of all lengths 2, 3, . . . , n − 1. m,m − e. Note that n = 2m + 1 ≥ 7. Then d(u, V (D) \ {x}) + d(v, V (D) \ {x}) ≤ 4m = 2n − 2. Therefore, by (5), d(x, {u, v}) ≥ 3. This, since m ≥ 3, in turn, implies that every partite set of H contains at least two vertices such that each of them together with x forms a 2-cycle. Therefore, there exist two vertices z, w ∈ V (H) such that z ↔ w, z ↔ x and w ↔ x Then, since for every k, k ∈ [1, m] there is a cycle of length 2k passing through the arc z → w, it follows that D contains cycles of all lengths 2, 3, . . . , n. The claim is proved. We now return to the proof of Theorem 4.9. From (5) it also follows that d(u, V (D) \ {x}) + d(v, V (D) \ {x}) ≥ 2(n − 1) − 1. Then, since H is strongly connected, from Theorem 3.7 it follows that either H contains cycles of all lengths 3, 4, . . . , n − 1 or H ∈ {K∗m,m, K∗m,m − e}∪ Φkn−1, where n/2 < k ≤ n − 2. In order to complete the proof of the theorem, by the above claim it suffices to consider only Proof. Let {u, v} be an arbitrary pair of non-adjacent vertices in K∗ S. Darbinyan 29 the case when H ∈ Φkn−1. From the definition of the set Φkn−1 it follows that H contains cycles of all lengths 2, 3, . . . , n − 1 except the cycle of length k. Let x1xn−1xn−2 . . . x2x1 be a Hamiltonian cycle in H. Since H ∈ Φkn−1, it follows that {x1, xk}, {xn−k, xn−1} are two distinct pairs of non-adjacent vertices other than {x, y} and d(x1, V (H)) + d(xk, V (H)) = d(xn−k, V (H)) + d(xn−1, V (H)) = 2n − 3. This together with (5) implies that d(x, {x1, xn−k, xk, xn−1) = 8. If k 6= n − 3, then x1 → xn−3 and x1xn−3xn−4 . . . xn−kxx1 is a cycle of length k. Assume that k = n − 3. Then {x1, xn−3}, {x3, xn−1} are two pairs of non-adjacent vertices other than {x, y}. We have that d(x, {x1, x3, xn−3, xn−1) = 8, x1 → xn−4 and x3 → xn−1. If x2 → x, then x1xn−4...x3x2xx1 is a cycle of length n − 3. Assume that x2x /∈ A(D). Then, since the vertices x2 and xn−2 are not adjacent and d(x2) + d(xn−2) ≥ 2n + 1, it is not difficult to see that x2 → xn−3 and x → x2. Therefore, xx2xn−3xn−4x3x is a cycle of length n − 3. This completes the proof of the theorem. In view of Theorem 4.9, it is natural to set the following problem. Problem: Let D be a 2-strongly connected digraph of order n satisfying condition (M ). Sup- pose that {x, y} is a pair of non-adjacent vertices in D such that 2n−3 ≤ d(x)+d(y) ≤ 2n−2. Whether D contains cycles of all lengths 3, 4, . . . , n − 1? 5. Remarks In the following, we suppose, further, that D is a 2-strongly connected digraph of order n satisfying condition (M ). Moreover, D contains a pair {y, z} of non-adjacent distinct vertices y, z such that d(y)+d(z) ≤ 2n−4. In this section, we will prove a number of properties of D. Lemma 5.1: Let x1x2 . . . xn−2zx1 be a cycle of length n − 1 in D, which does not contain y. Suppose that xa → xb, xq → y → xp and xt → y → xs, where 1 ≤ s ≤ a < p ≤ q < b ≤ t ≤ n − 2. Then D is Hamiltonian. Proof. Suppose, on the contrary, that D is not Hamiltonian. By Theorem 4.2, D contains no cycle passing through y and z. Notice that there are no integers l and r, 1 ≤ l < r ≤ n−2, such that xl → y → xr (for otherwise, x1 . . . xlyxr . . . xn−2zx1 is a cycle passing through y and z. If z → xi with i ∈ [a + 1, q], then C(y, z) = xs . . . xaxb . . . xn−2zxi . . . xqyxs; if xj → z with j ∈ [p, b − 1], then C(y, z) = x1 . . . xaxb . . . xtyxp . . . xjzx1. Thus, in both cases we have a contradiction. Therefore, d+(z, {xa+1, . . . , xq}) = d−(z, {xp, . . . , xb−1}) = 0, in particular, d(z, {xp, . . . , xq}) = 0 and the vertices z and xp are not adjacent. The last equality together with the fact that D contains at most one cycle of length two passing through z (Corollary 4.7) implies that d(z) = d(z, {x1, . . . , xp−1})+d(z, {xq+1, . . . , xn−2}) ≤ p−1+n−2−q +1 = n+p−q−2. (6) 30 On the Manoussakis Conjecture for a Digraph to be Hamiltonian Now we consider the vertex xp. It is easy to see that if xi → xp with i ∈ [1, s − 1], then C(y, z) = x1 . . . xixp . . . xqyxs . . . xaxb . . . xn−2zx1, if xp → xj with j ∈ [t + 1, n − 2], then C(y, z) = x1 . . . xaxb . . . xtyxp xj . . . xn−2zx1. In both cases we have a contradiction. Therefore, we may assume that d−(xp, {x1, . . . , xs−1}) = d+(xp, {xt+1, . . . , xn−2}) = 0. This implies that d(xp) = d +(xp, {x1, . . . , xs−1}) + d−(xp, {xt+1, . . . , xn−2}) + d(xp, {xs, . . . , xt}) + d(xp, {y}) ≤ s − 1 + n − 2 − t + 2(t − s + 1) = n + t − s − 1. (7) Without loss of generality, we may assume that s, q are chosen as maximal as possible and p, t are chosen as minimal as possible. Then d(y, {xs+1, . . . , xp−1}) = d(y, {xq+1, . . . , xt−1}) = 0. This, since D contains at most one cycle of length two passing through y, implies that d(y) = d(y, {x1, . . . , xs}) + d(y, {xp, . . . , xq}) + d(y, {xt, . . . , xn−2}) ≤ s + q − p + 1 + n − 2 − t + 1 + 1 = n + s + q − p − t + 1. (8) Since {y, z} and {xp, z} are two distinct pairs of non-adjacent vertices, from (6), (7), (8) and condition (M ) it follows that 4n − 3 ≤ d(y) + 2d(z) + d(xp) ≤ 4n − 4 − (q − p) ≤ 4n − 4, which is a contradiction. Lemma 5.1 is proved. The following claim is an immediate consequence of Lemma 5.1. Claim 1: Let x1x2 . . . xn−2zx1 be a cycle of length n − 1 in D passing through z. If xn−2 → y → x1 and x1 → xn−2, then D is Hamiltonian. The following claim will be very useful in the remaining proof. Claim 2: Let x1x2 . . . xn−2 be a Hamiltonian path in D − {y, z}. Suppose that for every pair of integers i and j, 1 ≤ i < j ≤ n − 2, if xi → y, then yxj /∈ A(D), and if xi → z, then zxj /∈ A(D). Then either D is Hamiltonian or for every k ∈ [2, n − 3], the following holds: A({x1, x2, . . . , xk−1} → {xk+1, xk+2, . . . , xn−2}) 6= ∅. Proof. Suppose, on the contrary, that D is not Hamiltonian and there is an integer k ∈ [2, n − 3] such that A({x1, x2, . . . , xk−1} → {xk+1, xk+2, . . . , xn−2}) = ∅, (9) We can assume that the vertices xm and xl are chosen so that y → xm, z → xl and d+(y, {xm+1, . . . , xn−2}) = d+(z, {xl+1, . . . , xn−2}) = 0. S. Darbinyan 31 Without loss of generality, we assume that m ≤ l. Since D is 2-strongly connected, it follows that 2 ≤ m ≤ l ≤ n − 3. From the supposition of this claim and (9) it follows that: (i) if k ≤ m or k ≥ l, then (respectively) A({x1, x2, . . . , xk−1} → {y, z, xk+1, xk+2, . . . , xn−2}) = ∅ or A({y, z, x1, x2, . . . , xk−1} → {xk+1, xk+2, . . . , xn−2}) = ∅, (ii) if m + 1 ≤ k ≤ l − 1, then A({y, x1, x2, . . . , xk−1} → {z, xk+1, xk+2, . . . , xn−2}) = ∅. Thus, in each case we have that D − xk is not strongly connected, which contradicts that D is 2-strongly connected. Claim 2 is proved. Lemma 5.2: Suppose that x1x2 . . . xn−2zx1 is a cycle in D passing through z and avoiding y. If xn−2 → y → x1, then D is Hamiltonian. Proof. Suppose, on the contrary, that xn−2 → y → x1 but D is not Hamiltonian. By Theorem 4.2, D contains no cycle passing through y and z in D. It is easy to see that the conditions of Claim 2 hold. Let xk → y → xp, where 2 ≤ p ≤ k ≤ n − 3, k minimal and p maximal with this property. Since D is 2-strongly connected, from Lemma 5.1 it follows that p ≤ k − 1. This means that there is no cycle of length two passing through y. By symmetry between the vertices y and z, we may assume that also there is no cycle of length two passing through z. Case 1. p = k − 1. By Lemma 5.1 we have that A({x1, . . . , xp−1} → {xk+1, . . . , xn−2}) = ∅. Then, by Claim 2, there are some integers i ∈ [1, p − 1] and j ∈ [k + 1, n − 2] such that xi → xk and xk−1 → xj. Therefore, C(y, z) = x1 . . . xixkyxk−1xj . . . xn−2zx1 is a cycle passing through y and z, which is a contradiction. Case 2. p ≤ k − 2. Then d(y, {xp+1, . . . , xk−1}) = 0. By Lemma 5.1 we have that A({x1, . . . , xp−1} → {xk+1, . . . , xn−2}) = ∅. (10) Therefore, by Claim 2, there are s ∈ [1, p−1], a ∈ [p + 1, k], b ∈ [p, k−1] and t ∈ [k + 1, n−2] such that xs → xa and xb → xt. If a > b, then x1 . . . xsxa . . . xkyxp . . . xbxt . . . xn−2zx1 is a cycle passing through y and z, which is a contradiction. We may therefore assume that a ≤ b. Then p + 1 ≤ a ≤ b ≤ k − 1 and the vertices y and xa are not adjacent. Choose (i) a and t as maximal as possible and (ii) choose b and s as minimal as possible, subject to (i). This means that A({x1, . . . , xp−1} → {xa+1, . . . , xn−2}) = A({x1, . . . , xb−1} → {xk+1, . . . , xn−2}) = ∅. (11) From the minimality of s and the maximality of t we have that d(xa) = d +(xa, {x1, . . . , xs−1}) + d−(xa, {xt+1, . . . , xn−2}) + d(xa, {xs, . . . , xt}) + d(xa, {z}) ≤ s − 1 + n − 2 − t + 2t − 2s + 1 = n + t − s − 2. (12) 32 On the Manoussakis Conjecture for a Digraph to be Hamiltonian Let m be the number of vertices of the set {xs+1, . . . , xp, xk, . . . , xt−1}, which are not adjacent to y. Then, since y is not on the cycle of length two and d(y, {xp+1, . . . , xk−1}) = 0, it follows that d(y) ≤ n − 2 − m − (k − 1 − p) = n + p − m − k − 1. (13) Assume first that d+(z, {xs+1, . . . , xp}) = d−(z, {xk, . . . , xt−1}) = 0. From this and taking into account Lemma 4.5 (there is no path of length two between y and z) we obtain that d(z) ≤ s + n − 2 − t + 1 + m + k − 1 − p = n + k + m + s − t − p − 2. (14) Combining (12)-(14), k − p ≥ 2 and m ≥ 0, we obtain 2d(y) + d(xa) + d(z) ≤ 4n − 6 − (k − p) − m ≤ 4n − 8, which is a contradiction to condition (M ), since {y, z} and {y, xa} are two distinct pairs of non-adjacent vertices. Assume next that d+(z, {xs+1, . . . , xp}) 6= 0 or d−(z, {xk, . . . , xt−1}) 6= 0, i.e., there is a q ∈ [s + 1, p] such that z → xq or there is a r ∈ [k, t − 1] such that xr → z. Using Claim 2, we obtain that A({x1, . . . , xa−1} → {xa+1, . . . , xn−2}) 6= ∅. Let xs1 → xt1 , where s1 ∈ [1, a − 1] and t1 ∈ [a + 1, n − 2]. From (11) it follows that s1 ∈ [p, a − 1] and t1 ∈ [a + 1, k]. Choose t1 maximal with this property. Then A({x1, . . . , xa−1} → {xt1+1, . . . , xn−2}) = ∅. (15) Now using the facts that z → xq or xr → z, it is not difficult to check that: if t1 > b, then C(y, z) = x1 . . . xsxa . . . xbxt . . . xn−2zxq . . . xs1 xt1 . . . xkyx1 or C(y, z) = x1 . . . xsxa . . . xbxt . . . xn−2yxp . . . xs1 xt1 . . . xrzx1 is a cycle passing through y and z, when z → xq and xr → z, respectively. In both cases we have a contradiction. We may therefore assume that t1 ≤ b. From Claim 2 we have that A({x1, . . . , xt1−1} → {xt1+1, . . . , xn−2}) 6= ∅. Let xs2 → xt2 , where s2 ∈ [1, t1 −1] and t2 ∈ [t1 + 1, n−2]. From (11) and (15) it follows that s2 ∈ [a, t1 −1] and t2 ∈ [t1 + 1, k]. Choose t2 maximal with this property. Then A({x1, . . . , xt1−1} → {xt2+1, . . . , xn−2}) = ∅. (16) If t2 > b, then C(y, z) = x1 . . . xsxa . . . xs2 xt2 . . . xkyxp . . . xs1 xt1 . . . xbxt . . . xn−2zx1, a contra- diction. We may therefore assume that t2 ≤ b. In particular, from t2 ≥ t1 + 1 it follows that t1 < b. Using Claim 2, (11) and (16), we obtain that there are some integers s3 ∈ [t1, t2 − 1] and t3 ∈ [t2 + 1, k] such that xs3 → xt3 . Choose t3 maximal with this properties. Then A({x1, . . . , xt2−1} → {xt3+1, . . . , xn−2}) = ∅. (17) S. Darbinyan 33 If t3 > b, then C(y, z) = x1 . . . xsxa . . . xs2 xt2 . . . xbxt . . . xn−2zxq . . . xs1 xt1 . . . xs3 xt3 . . . xkyx1 or C(y, z) = x1 . . . xsxa . . . xs2 xt2 . . . xbxt . . . xn−2yxp . . . xs1 xt1 . . . xs3 xt3 . . . xrzx1, when z → xq or xr → z, respectively. We may therefore assume that t3 ≤ b. Then t2 < b. Again using Claim 2, (11) and (17), we obtain that there are some integers s4 ∈ [t2, t3 − 1] and t4 ∈ [t3 + 1, k] such that xs4 → xt4 . If t4 > b, then C(x, y) = x1 . . . xs0 xt0 . . . xs2 xt2 . . . xs4 xt4 . . . xkyxp . . . xs1 xt1 . . . xs3 xt3 . . . xbxt . . . xn−2zx1, a contradic- tion. (Here, xs := xs0 and xa = xt0 ). Continuing this process, we finally conclude that for some l ≥ 0, tl > b since all the ver- tices xt0 , xt1 , . . . , xtl are distinct and in {xp, . . . , xk}. By the above arguments we have that: if tl is even, then C(y, z) = x1 . . . xs0 xt0 . . . xs2 xt2 . . . xs4 xt4 . . . xsl xtl . . . xkyxp . . . xs1 xt1 . . . xs3 xt3 . . . xsl−1 xtl−1 . . . xbxt . . . xn−2zx1, if l is odd, then C(y, z) = x1 . . . xs0 xt0 . . . xs2 xt2 . . . xsl−1 xtl−1 . . . xbxt . . . xn−2zxq . . . xs1 xt1 . . . xs3 xt3 . . . xsl xtl . . . xkyx1, or C(y, z) = x1 . . . xs0 xt0 . . . xs2 xt2 . . . xsl−1 xtl−1 . . . xbxt . . . xn−2yxp . . . xs1 xt1 . . . xs3 xt3 . . . xsl xtl . . . xrzx1, when z → xq or xr → z, respectively. In all cases we have a cycle passing through y and z, which contra- dicts our supposition. Lemma 5.2 is proved. From Theorem 4.4, Lemma 5.2 and Corollary 4.7 the following corollary follows. Corollary 5.3: If D is not Hamiltonian, then max{d(y), d(z)} ≤ n − 2. Lemma 5.4: Let C = x1x2 . . . xn−3x1 be a cycle of length n − 3 in D passing through y and avoiding z. Let V (D) \ V (C) = {z, u, v}. If (i). d(y, {u, v}) = 0 and zuvz is a cycle of length 3 or (ii). d(y) ≤ n − 3 and z ↔ u, then D is Hamiltonian. Proof. Suppose, on the contrary, that D is not Hamiltonian. Then, by Theorem 4.2, D contains no cycle passing through y and z. (i). Since d(y, {z, u, v}) = 0 and through y there is at most one cycle of length two, it follows that d(y) ≤ n − 3. It is easy to see that for every i ∈ [1, n − 3] the following holds: −→a [xi, z] + −→a [v, xi+1] ≤ 1, −→a [xi, u] + −→a [z, xi+1] ≤ 1 and −→a [xi, v] + −→a [u, xi+1] ≤ 1, (for otherwise, D is Hamiltonian). Therefore, d(z, V (C)) + d(u, V (C)) + d(v, V (C)) = n−3∑ i=1 (−→a [xi, z] + −→a [v, xi+1] + −→a [xi, u] + −→a [z, xi+1] + −→a [xi, v] + −→a [u, xi+1]) ≤ 3n − 9. Then, since d(z, {u, v}) ≤ 3 and d(u, {z, v}) + d(v, {u, z}) ≤ 7 it follows that d(z) + d(u) + d(v) ≤ 3n + 1. Therefore, since 2d(y) + d(z) + d(u) ≥ 4n − 3 and d(v) + d(y) ≥ 2n + 1, we have 6n − 2 ≤ 3d(y) + d(u) + d(v) + d(z) ≤ 6n − 8, which is a contradiction. (ii). Then for every i ∈ [1, n − 3] we have −→a [xi, z] + −→a [u, xi+1] ≤ 1 and −→a [xi, u] +−→a [z, xi+1] ≤ 1. Therefore, d(z, V (C)) + d(u, V (C)) = n−3∑ i=1 (−→a [xi, z] + −→a [u, xi+1] + −→a [xi, u] + −→a [z, xi+1]) ≤ 2n − 6. 34 On the Manoussakis Conjecture for a Digraph to be Hamiltonian Hence, d(z) + d(u) ≤ 2n + 1. This together with d(y) ≤ n − 3 and condition (M ) gives 4n − 3 ≤ d(z) + d(u) + 2d(y) ≤ 2n + 1 + 2n − 6 = 2n − 5, which is a contradiction. Lemma 5.4 is proved. Lemma 5.5: Let C := x1x2 . . . xn−4x1 be a cycle of length n− 4 in D passing through y and avoiding z. Let V (D) \ V (C)) = {z, u1, u2, u3}. If one of the following conditions holds (i). d(y) ≤ n − 3 and z ↔ u1 , ii). zu1u2z is a cycle of length 3 and d(y, {u1, u2}) = 0, (iii). zu1u2u3z is a cycle of length 4 and d(y, {u1, u2, u3}) = 0, then D is Hamiltonian. Proof. Suppose, on the contrary, that D is not Hamiltonian. By Theorem 4.2, D contains no cycle passing through y and z. (i). Note that y and u1 are not adjacent by Lemma 4.5. Since z ↔ u1, it is easy to see that −→a [xi, z] + −→a [u1, xi+1] ≤ 1 and −→a [xi, u1] + −→a [z, xi+1] ≤ 1. Hence, d(z, V (C)) + d(u1, V (C)) ≤ 2n − 8. Therefore, since, d(u1, {z, u2, u3}) ≤ 6 and d(z, {u1, u2, u3}) ≤ 4, we have d(z) + d(u1) ≤ 2n + 2. This together with d(y) ≤ n − 3 and condition (M ) implies that 4n − 3 ≤ d(z) + 2d(y) + d(u1) ≤ 4n − 4, which is a contradiction. (ii). Then it is easy to see that −→a [xi, z] + −→a [u2, xi+1] ≤ 1, −→a [xi, u1] + −→a [z, xi+1] ≤ 1 and −→a [xi, u2] + −→a [u1, xi+1] ≤ 1. Hence, d(z, V (C)) + d(u1, V (C)) + d(u2, V (C)) ≤ 3n − 12. Therefore, since d(z, {u1, u2, u3}) ≤ 4 and d(u1, {z, u2, u3}) + d(u2, {z, u1, u3}) ≤ 11, we obtain that d(z) + d(u1) + d(u2) ≤ 3n + 3. This together with d(y, {z, u1, u2}) = 0 implies that d(y) ≤ n − 3 and d(z) + d(u1) + d(u2) + 3d(y) ≤ 6n − 6. On the other hand, since d(z) + d(u1) + 2d(y) ≥ 4n − 3 and d(y) + d(u2) ≥ 2n + 1, we have 6n − 2 ≤ d(z) + d(u1) + 3d(y) + d(u2) ≤ 6n − 6, which is a contradiction. (iii). First, notice that d(y) ≤ n − 4. By an argument similar to that in the proof of (ii), we can show that d(z, V (Cn−4)) + d(u1, V (Cn−4)) + d(u2, V (Cn−4)) + d(u3, V (Cn−4)) ≤ 4n − 16. Then, since d(z, {u1, u2, u3}) + d(u1, {z, u2, u3}) + d(u2, {u1, u2, z}) + d(u3, {u1, u2, z}) ≤ 20, we have d(z) + d(u1) + d(u2) + d(u3) ≤ 4n + 4. Besides, from condition (M ) and d(y) ≤ n−4 it follows that 8n − 6 ≤ d(z) + 4d(y) + d(u1) + d(u2) + d(u3) ≤ 8n − 12, S. Darbinyan 35 which is a contradiction. Lemma 5.5 is proved. Lemma 5.6: Let C := x1x2 . . . xn−5x1 be a cycle of length n− 5 in D passing through y and avoiding z. Let A = V (D) \ V (C)) = {z, u1, u2, u3, u4}. If d(y, {u1, u2}) = 0 and zu1u2z is a cycle of length three, then D is Hamiltonian. Proof. Suppose, on the contrary, that D is not Hamiltohian. By Theorem 4.2, D contains no cycle passing through y and z. Then d(y) ≤ n−3. It is easy to see that for all i ∈ [1, n−5], −→a [xi, z] + −→a [u2, xi+1] ≤ 1, −→a [xi, u1] + −→a [z, xi+1] ≤ 1 and −→a [xi, u2] + −→a [u1, xi+1] ≤ 1. Therefore, d(z, V (C)) + d(u1, V (C)) + d(u2, V (C)) = n−5∑ i=1 (−→a [xi, z] +−→a [u2, xi+1] +−→a [xi, u1] +−→a [z, xi+1] +−→a [xi, u2] + −→a [u1, xi+1]) ≤ 3n − 15. Since d(z, A) ≤ 5 and d(u1, A) + d(u2, A) ≤ 15, it follows that d(z) + d(u1) + d(u2) ≤ 3n + 5. This together with d(y) ≤ n − 3, d(y) + d(u2) ≥ 2n + 1 and condition (M ) implies that 6n − 2 ≤ d(z) + 3d(y) + d(u1) + d(u2) ≤ 6n − 4, which is a contradiction. This proves Lemma 5.6. Lemma 5.7: Suppose that C := x1x2 . . . xn−2x1 is a cycle of length n − 2 in D passing through y and avoiding z. Let V (D) \ V (C)) = {z, u}. If u ↔ z, then D is Hamiltonian. Proof. Suppose, on the contrary, that z ↔ x but D is not Hamiltonian. Then, by Lemma 4.5, the vertices y and x are not adjacent. Hence, d(y) ≤ n− 2. Since D is not Hamiltonian, it follows that for every i ∈ [1, n − 2] we have −→a [xi, z] + −→a [x, xi+1] ≤ 1 and −→a [xi, x] +−→a [z0, xi+1] ≤ 1. These imply that d(z) + d(x) ≤ 2n. Therefore, by condition (M ), we have 4n − 3 ≤ d(z) + d(x) + 2d(y) ≤ 4n − 4, which is a contradiction. Lemma 5.7 is proved. 6. Conclusion In the current article, we have examined the Manoussakis conjecture for a digraph to be Hamiltonian. For a digraph with the conditions of the Manoussakis conjecture, a number of theorems and lemmas are proved. Found results may be the first step towards confirming the Manoussakis conjecture. Added in proof. Recently, using some results of this paper, the author confirmed the Manoussakis conjecture. Acknowledgement The author would like to thank the referees for careful reading and many helpful remarks and suggestions. 36 On the Manoussakis Conjecture for a Digraph to be Hamiltonian References [1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer- Verlag, London, 2000. [2] J.-C. Bermond and C. Thomassen, “Cycles in digraphs- A survey”, J. Graph Theory, vol. 5, pp.1-43, 1981. [3] D. Küh and D. Ostus, “A survey on Hamilton cycles in directed graphs”, European J. Combin., vol. 33, pp. 750-766, 2012. [4] M. Meyniel, “Une condition suffisante d’existence d’un circuit Hamiltonien dans un graphe oriente”, J. Combinatorial Theory B, vol. 14, pp. 137-147, 1973. [5] Y. Manoussakis, “Directed Hamiltonian graphs”, J. Graph Theory, vol. 16, no. 1, pp. 51-59, 1992. [6] S. Kh. Darbinyan, “Disproof of a conjecture of Thomassen”, Akad. Nauk Armyan. SSR Dokl., vol. 76, no. 2, pp. 51-54, 1983. [7] S. Kh. Darbinyan, “On Hamiltonian and Hamilton-connected digraphs”, Akad. Nauk Armyan. SSR Dokl., vol. 91, no. 1, pp. 3-6, 1990 (for a detailed proof see arXiv: 1801.05166v1, 16 Jan 2018. [8] B. Ning, “Notes on a conjecture of Manoussakis concerning Hamilton cycles in digraphs, electronic preprint”, arXiv:1404.5013v1 [math.CO] 20 Apr 2014, pp. 8. [9] R. Häggvist and C. Thomassen, “On pancyclic digraphs”,J. Combin. Theory B, vol. 20, pp. 20-40, 1976. [10] J. A. Bondy and C. Thomassen, “A short proof of Meyniel’s theorem’, Discrete Math., vol. 19, pp. 195-197, 1977. [11] J. A. Bondy, “Basic Graph Theory: Paths and Circuits”, In Handbook of Combinatorics, vol. 1-2, Elsevier, Amsterdam, 1995. [12] A.Yeo, “How close to regular must a semicomplete multipartite digraph to be secure Hamiltonisity?”, Graphs Combin., vol. 15, pp. 481-493, 1999. [13] S. Kh. Darbinyan, “On pancyclic digraphs”, Preprint of the Computing Center of Akademy of Sciences of Armenia, 21 pages, 1979. [14] S. Kh. Darbinyan, “Pancyclicity of digraphs with the Meyniel condition”, Studia Sci. Math. Hungar., vol. 20, no. 1-4, pp. 95-117, 1985. (Ph.D. Thesis, Institute Mathematici Akad. Nauk BSSR, Minsk, 1981). [15] A. Benhocine, “Pancyclism and Meyniel’s conditions”, Discrete Math., vol. 58, pp. 113- 120, 1986. [16] F. Harary and L. Moser, “The theory of round robin tournaments”, Amer. Math. Monthly, vol. 73, pp. 231-246, 1966. Submitted 14.12.2018, accepted 18.04.2019. S. Darbinyan 3 7 ÎáÕÙÝáñáßí³Í ·ñ³ýÇ Ñ³ÙÇÉïáÝÛ³ÝáõÃÛ³Ý í»ñ³µ»ñÛ³É Ø³Ýááõë³ÏÇëÇ í³ñϳÍÇ Ù³ëÇÝ ê³Ùí»É Ê. ¸³ñµÇÝÛ³Ý ÐÐ ¶²² ÆÝýáñÙ³ïÇϳÛÇ ¨ ³íïáÙ³ï³óÙ³Ý åñáµÉ»ÙÝ»ñÇ ÇÝëïÇïáõï e-mail: samdarbin@ipia.sci.am ²Ù÷á÷áõ٠سÝááõë³ÏÇëÁ (J. of Graph Theory, vol. 16, pp. 51-59, 1992) ³é³ç³ñÏ»É ¿ Ñ»ï¨Û³É í³ñϳÍÁ: ì³ñϳÍ: ¸Çóáõù D-Ý 2-áõÅ»Õ Ï³å³Ïóí³Í n-·³·³Ã³ÝÇ ÏáÕÙÝáñáßí³Í ·ñ³ý ¿: ºÃ» D-Ç ó³Ýϳó³Í áã ÏÇó ·³·³ÃÝ»ñÇ ó³Ýϳó³Í »ñÏáõ ï³ñµ»ñ fx; yg ¨ fu; vg ½áõÛ·»ñÇ Ñ³Ù³ñ ï»ÕÇ áõÝÇ Ñ»ï¨Û³É d( x ) + d ( y ) + d ( w ) + d( z ) ¸ 4 n ¡ 3 ³Ýѳí³ë³ñáõÃÛáõÝÁ, ³å³ D-Ý Ñ³Ý¹Çë³ÝáõÙ ¿ ѳÙÇÉïáÝÛ³Ý: Ü»ñϳ ³ß˳ï³ÝùáõÙ ³å³óáõóí»É ¿, áñ »Ã» D ÏáÕÙÝáñáßí³Í ·ñ³ýÁ µ³í³ñ³ñáõÙ ¿ سÝááõë³ÏÇëÇ í³ñϳÍÇ å³ÛÙ³ÝÝ»ñÇÝ, ³å³ (1). D ·ñ³ýÁ å³ñáõݳÏáõÙ ¿ óÇÏÉ-ý³Ïïáñ; (2). ºÃ» D-Ç áã ÏÇó ·³·³ÃÝ»ñÇ áñ¨¿ fx; yg ½áõÛ·Ç Ñ³Ù³ñ d( x ) + d( y ) · 2 n ¡ 2 , ³å³ (i) D-Ý Ñ³ÙÇÉïáÝÛ³Ý ¿ ³ÛÝ ¨ ÙdzÛÝ ³ÛÝ Å³Ù³Ý³Ï, »ñµ D-Ý å³ñáõݳÏáõÙ x ¨ y ·³·³ÃÝ»ñáí ³ÝóÝáÕ ÏáÕÙÝáñáßí³Í óÇÏÉ; (ii) D-Ý Ñ³ÙÇÉïáÝÛ³Ý ¿ ϳ٠å³ñáõݳÏáõÙ ¿ x ( y ) ·³·³Ãáí ³ÝóÝáÕ n ¡ 1 »ñϳñáõÃÛ³Ý ÏáÕÙÝáñáßí³Í óÇÏÉ, áñÁ ãÇ ³ÝóÝáõÙ y ( x ) ·³·³Ãáí (Ù³ëݳíáñ³å»ë, D-Ý å³ñáõݳÏáõÙ ¿ ³éÝí³½Ý n ¡ 1 »ñϳñáõÃÛ³Ý óÇÏÉ) ; (3). ºÃ» D-Ç áã ÏÇó ·³·³ÃÝ»ñÇ áñ¨¿ fx; yg ½áõÛ·Ç Ñ³Ù³ñ d ( x) + d( y ) · 2 n ¡ 4 , ³å³ ó³Ýϳó³Í k, 2 · k · n ¡ 1 , ³ÝµáÕç ÃíÇ Ñ³Ù³ñ D-Ý å³ñáõݳÏáõÙ ¿ k »ñϳñáõÃÛ³Ý ÏáÕÙÝáñáßí³Í óÇÏÉ; (4). D ·ñ³ýÇ áñáß³ÏÇ »ñϳñáõÃÛáõÝÝ»ñ ( n¡ 5 ) -Çó ÙÇÝ㨠( n¡ 1 ) áõÝ»óáÕ ÏáÕÙÝáñáßí³Í ÏáÕÙÝáñáßí³Í ·ñ³ý: Î ãèïîòåçå Ìàíîóññàêèñà î ãàìèëüòîíîâîñòè îðãðàôîâ Ñàìâåë Õ. Äàðáèíÿí Èíñòèòóò ïðîáëåì èíôîðìàòèêè è àâòîìàòèçàöèè ÍÀÍ ÐÀ e-mail: samdarbin@ipia.sci.am Àííîòàöèÿ Ìàíîóññàêèñ (J. of Graph Theory, vol. 16, pp. 51-59, 1992) ïðåäëîæèë ñëåäóþùóþ ãèïîòåçó. Ãèïîòåçà: Ïóñòü D ÿâëÿåòñÿ 2-ñèëüíî ñâÿçíûì n-âåðøèííûì îðãðàôîì, â êîòîðîì äëÿ ëþáûõ ðàçëè÷íûõ ïàð fx; yg, fu; vg íåñìåæíûõ âåðøèí èìååò ìåñòî óÇÏÉ»ñÇ Ñ³Ù³ñ ³å³óáõóí»É »Ý ÙÇ ß³ñù åݹáõÙÝ»ñ: ´³Ý³ÉÇ µ³é»ñ՝ ÏáÕÙÝáñáßí³Í ·ñ³ý, ѳÙÇÉïáÝÛ³Ý óÇÏÉ, ý³Ïïáñ óÇÏÉ, ѳÙóÇÏÉÇÏ 3 8 On the Manoussakis Conjecture for a Digraph to be Hamiltonian d( x ) + d( y ) + d( w ) + d ( z ) ¸ 4 n ¡ 3 . Òîãäà D ÿâëÿåòñÿ ãàìèëüòîíîâûì.  íàñòîÿùåé ðàáîòå äîêàçàíî, ÷òî åñëè îðãðàô D óäîâëåòâîðÿåò óñëîâèÿì ãèïîòåçà Ìàíîóññàêèñà, òî (1). D ñîäåðæèò öèêë-ôàêòîð; (2). Åñëè äëÿ íåêîòîðîé ïàðû íåñìåæíûõ âåðøèí x è y èìååò ìåñòî d( x ) + d( y ) · 2 n ¡ 2 , òî èìåþò ìåñòî: (i) D ÿâëÿåòñÿ ãàìèëüòîíîâûì òîãäà è òîëüêî òîãäà, êîãäà D ñîäåðæèò êîíòóð ïðîõîäÿùèé ÷åðåç âåðøèí x è y, (ii) D ÿâëÿåòñÿ ãàìèëüòîíîâûì èëè ñîäåðæèò êîíòóð äëèíû n ¡ 1 , êîòîðûé ïðîõîäèò ÷åðåç âåðøèíó x ( y ) (â ÷àñòíîñòè, D ñîäåðæèò êîíòóð äëèíû ïî êðàéíåé ìåðå n ¡ 1 ); (3). Åñëè äëÿ íåêîòîðîé ïàðû íåñìåæíûõ âåðøèí x è y èìååò ìåñòî d( x ) + d( y ) · 2 n ¡ 4 , òî D ñîäåðæèò êîíòóð ëþáîé äëèíû k, 3 · k · n ¡ 1 ; (4). Äîêàçàíû ðÿä ñâîéñòâ äëÿ êîíòóðîâ äëèíû îò n ¡ 5 äî n ¡ 1 . Êëþ÷åâûå ñëîâà: îðãðàô, ãàìèëüòîíîâûé öèêë, ôàêòîð öèêë, ïàíöèêëè÷åñêèé îðãðàô. 2_ 2_Darbinyan_Article