Mathematical Problems of Computer Science 55, 9–25, 2021. UDC 519.1 A Theorem on Even Pancyclic Bipartite Digraphs Samvel Kh. Darbinyan Institute for Informatics and Automation Problems of NAS RA e-mail: samdarbin@iiap.am Abstract We prove a Meyniel-type condition and a Bang-Jensen, Gutin and Li-type condition for a strongly connected balanced bipartite digraph to be even pancyclic. Let D be a balanced bipartite digraph of order 2a ≥ 6. We prove that (i) If d(x)+d(y) ≥ 3a for every pair of vertices x, y from the same partite set, then D contains cycles of all even lengths 2, 4, . . . , 2a, in particular, D is Hamiltonian. (ii) If D is other than a directed cycle of length 2a and d(x) + d(y) ≥ 3a for every pair of vertices x, y with a common out-neighbor or in-neighbor, then either D contains cycles of all even lengths 2, 4, . . . , 2a or d(u) + d(v) ≥ 3a for every pair of vertices u, v from the same partite set. Moreover, by (i), D contains cycles of all even lengths 2, 4, . . . , 2a, in particular, D is Hamiltonian. Keywords: Digraphs, Hamiltonian cycles, Bipartite digraphs, Pancyclic, Even pancyclic. 1. Introduction In this paper, we consider finite digraphs without loops and multiple arcs. We assume that the reader is familiar with the standard terminology on digraphs and refer the reader to [1]. Every cycle and path is assumed simple and directed. A cycle in a digraph D is called Hamiltonian if it includes all the vertices of D. A digraph D is Hamiltonian if it contains a Hamiltonian cycle. A digraph D of order n ≥ 3 is pancyclic if it contains cycles of every length k, 3 ≤ k ≤ n. There are numerous sufficient conditions for the existence of a Hamiltonian cycle in a digraph (see, e.g., [1] - [10]). It was proved (see, e.g., [1], [6], [8], [9], [11] - [14]) that a number of sufficient conditions for a digraph (undirected graph) to be Hamiltonian are also sufficient for the digraph to be pancyclic (with some exceptions). For hamiltonicity, the more general and classical one is the following theorem due to M. Meyniel. Theorem 1: (Meyniel [10]). Let D be a strong 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. Notice that Meyniel’s theorem is a generalization of Ghouila-Houri’s and Woodall’s the- orems. 9 10 A Theorem on Even Pancyclic Bipartite Digraphs A digraph D is a bipartite if there exists a partition X, Y of its vertex set into two partite sets such that every arc of D has its end-vertices in different partite sets. It is called balanced if |X| = |Y |. Following [1], we will say that a balanced bipartite digraph D of order 2a is even pancyclic (note that a number of authors use the term ”bipancyclic” instead of ”even pancyclic”) if it contains cycles of all even lengths 4, 6, . . . , 2a. An analogue of Meyniel’s theorem for the hamiltonicity of balanced bipartite digraphs was given by Adamus et al. [3]. Theorem 2: (Adamus et al. [3]). Let D be a balanced bipartite digraph of order 2a ≥ 4. Then D is Hamiltonian provided one of the following holds: (a) d(x) + d(y) ≥ 3a + 1 for each pair of non-adjacent vertices x, y ∈ V (D); (b) D is strong and d(x) + d(y) ≥ 3a for each pair of non-adjacent vertices x, y ∈ V (D); (c) the minimal degree of D is at least (3a + 1)/2; (d) D is strong, and the minimal degree of D is at least 3a/2. Meszka [15] investigated the even pancyclicity of a balanced bipartite digraph satisfying a weaker condition than those in Theorem 2(a). He proved the following theorem. Theorem 3: (Meszka [15]). Let D be a balanced bipartite digraph of order 2a ≥ 4. Suppose that d(x) + d(y) ≥ 3a + 1 for each two distinct vertices x, y from the same partite set. Then D contains cycles of all even lengths 4, 6, . . . , 2a. Let x, y be a pair of distinct vertices in a digraph D. The pair {x, y} is a dominated pair (respectively, dominating pair) if there is a vertex z ∈ V (D) \ {x, y} such that z → {x, y} (respectively, {x, y} → z). We will say that a pair of vertices {u, v} is a good pair if it is dominated or dominating. In this case we will say that u (respectively, v) is a partner of v (respectively, u). In [5], Bang-Jensen et al. gave a new type condition for a digraph to be Hamiltonian. In the same paper, they also conjectured the following strengthening of Meyniel’s theorem. Conjecture 1: Let D be a strong digraph of order n. Suppose that d(x) + d(y) ≥ 2n − 1 for every good pair of non-adjacent distinct vertices x, y. Then D is Hamiltonian. They also conjectured that this can even be generalized to the following: Conjecture 2:. Let D be a strong digraph of order n. Suppose that d(x) + d(y) ≥ 2n − 1 for every pair of non-adjacent distinct vertices x, y with a common in-neighbor. Then D is Hamiltonian. In [5] and [4], it was proved that Conjecture 1 (2) is true if we also require an additional condition. Theorem 4: (Bang-Jensen et al. [5]). Let D be a strong digraph of order n ≥ 2. Suppose that min{d(x), d(y)} ≥ n − 1 and d(x) + d(y) ≥ 2n − 1 for any pair of non-adjacent vertices x, y with a common in-neighbor. Then D is Hamiltonian. In [4], it was proved that if in Conjecture 1 we replace the degree condition d(x)+d(y) ≥ S. Darbinyan 11 2n − 1 with d(x) + d(y) ≥ 5n/2 − 4, then Conjecture 1 is true. There are some versions of Conjecture 1 and 2 for balanced bipartite digraphs. (see, e.g., Theorems 5, 6 and 7). Theorem 5: (Adamus [2]). Let D be a strong balanced bipartite digraph of order 2a ≥ 6. If d(x) + d(y) ≥ 3a for every good pair of distinct vertices x, y, then D is Hamiltonian. An analogue of Theorem 4 was given by Wang [16], and recently strengthened by the author [17]. Theorem 6: (Wang [16]). Let D be a strong balanced bipartite digraph of order 2a ≥ 4. Sup- pose that, for every dominating pair of vertices {x, y}, either d(x) ≥ 2a−1 and d(y) ≥ a+1 or d(y) ≥ 2a − 1 and d(x) ≥ a + 1. Then D is Hamiltonian. Before stating the next theorem we need to define a digraph of order eight. Example 1: Let D(8) be the bipartite digraph with partite sets X = {x0, x1, x2, x3} and Y = {y0, y1, y2, y3}, and A(D(8)) contains exactly the arcs y0x1, y1x0, x2y3, x3y2 and all the arcs of the following 2-cycles: xi ↔ yi, i ∈ [0, 3], y0 ↔ x2, y0 ↔ x3, y1 ↔ x2 and y1 ↔ x3. It is not difficult to check that D(8) is strongly connected, max{d(x), d(y)} ≥ 2a − 1 for every pair of vertices {x, y} with a common out-neighbor, but it is not Hamiltonian. Indeed, if C is a Hamiltonian cycle in D(8), then C would contain the arcs x1y1 and x0y0 and therefore, the path x1y1x0y0 or the path x0y0x1y1, which is impossible since N−(x0) = N −(x1) = {y0, y1}. Theorem 7: (Darbinyan [17]). Let D be a strong balanced bipartite digraph of order 2a ≥ 8. Suppose that max{d(x), d(y)} ≥ 2a − 1 for every pair of distinct vertices {x, y} with a com- mon out-neighbor. Then D is Hamiltonian unless D is isomorphic to the digraph D(8). Motivated by the Bondy famous metaconjecture, the author, together with Karapetyan [20],proposed the following problem: Problem 1: Characterize those digraphs, which satisfy the conditions of Theorem 5 (or 6 or 7) but are not even pancyclic. This problem for Theorems 6 and 7 was solved by the author [18] (Theorem 8(ii)), and for Theorem 5 by Adamus [19] (Theorem 9). Theorem 8: Let D be a strong balanced bipartite digraph of order 2a. (i). (Darbinyan [18]). If D contains a cycle of length 2a − 2 and max{d(x), d(y)} ≥ 2a − 2 ≥ 6 for every pair of distinct vertices {x, y} with a common out-neighbor, then for every k, 1 ≤ k ≤ a − 1, D contains a cycle of length 2k. (ii). (Darbinyan [18]). If D is not a directed cycle of length 2a ≥ 8 and max{d(x), d(y)} ≥ 2a − 1 for every pair of distinct vertices {x, y} with a common out- neighbor, then for every k, 1 ≤ k ≤ a, D contains a cycle of length 2k (in particular, D is even pancyclic) unless D is isomorphic to the digraph D(8). 12 A Theorem on Even Pancyclic Bipartite Digraphs (iii). (Darbinyan and Karapetyan [20]). Suppose that D is not a directed cycle of length 2a ≥ 10 and max{d(x), d(y)} ≥ 2a − 2 for every pair of distinct vertices {x, y} with a com- mon out-neighbor. Then D contains a cycle of length 2a − 2 unless D is isomorphic to a digraph of order ten, which we specify. The following theorem by Adamus (Theorem 9) and the main result of this paper (The- orem 10) were proved simultaneously and independently. Theorem 9: (Adamus [19]). Let D be a balanced bipartite Hamiltonian digraph of order 2a ≥ 6 other than a directed cycle of length 2a. Suppose that d(x)+d(y) ≥ 3a for every good pair of distinct vertices x, y. Then D contains cycles of all even lengths 2, 4, . . . , 2a. Theorem 10: Let D be a strong balanced bipartite digraph of order 2a ≥ 6 with partite sets X and Y . If d(x) + d(y) ≥ 3a for every pair of distinct vertices {x, y} either both in X or both in Y , then D contains cycles of all even lengths less than or equal to 2a (in particular, D is Hamiltonian). The last result (Theorem 10) was presented at the ”International Conference Dedicated to 90th Anniversary of Sergey Mergelyan”, 20-25 May, 2018, Yerevan, Armenia. Using some arguments of [2] by Adamus, we can prove the following lemma. Lemma 1: Let D be a balanced bipartite digraph of order 2a ≥ 6 with partite sets X and Y . Suppose that D is not a directed cycle of length 2a and d(u) + d(v) ≥ 3a for every good pair of distinct vertices u, v. Then D either is even pancyclic or every pair of distinct vertices {x, y} from the same partite set is a good pair. The following theorem follows from Theorem 10 and Lemma 1. Theorem 11: Let D be a strong balanced bipartite digraph of order 2a ≥ 6 other than a directed cycle of length 2a. Suppose that d(x) + d(y) ≥ 3a for every good pair of distinct vertices x, y. Then D contains cycles of all even lengths 2, 4, . . . , 2a. It is worth to noting that in the proof of Theorem 10 does not use the fact that D is Hamiltonian. Thus, we have a common alternative proof for Theorems 2, 3, 5 and 9. Note that if a balanced bipartite digraph satisfies the condition of Theorem 2(a) (or Theorem 2(c)), then D is strong. Example 2: For any even integer a ≥ 2 there is a non-strongly connected balanced bipartite digraph D of order 2a with partite sets X and Y , such that d(x)+d(y) ≥ 3a for every pair of distinct vertices {x, y} either both in X or both in Y ,i.e., if D is not strong, then Theorem 10 is not true. To see this, we take two balanced bipartite complete digraphs both of order a (a is even) with partite sets U, V and Z, W , respectively. By adding all the possible arcs from Z to V and from W to U we obtain a digraph D. It is easy to check that d(x) + d(y) ≥ 3a for every pair of non-adjacent distinct vertices {x, y} of D, but D is not strongly connected and hence, D is not Hamiltonian. S. Darbinyan 13 2. Terminology and Notations In this paper, we consider finite digraphs without loops and multiple arcs. Terminology and notations not defined here or above are consistent with [1]. 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. If xy ∈ A(D), then we also write x → y and say that x dominates y or y is an out-neighbor of x and x is an in-neighbor of y. If x → y and y → x we shall use the notation x ↔ y (x ↔ y is called 2-cycle). We set −→a [x, y] = 1 if xy ∈ A(D) and −→a [x, y] = 0 if xy /∈ A(D). 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. Similarly, A ↔ B means that A → B and 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[A]. For integers a and b, a ≤ b, let [a, b] denote the set of all the 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 a 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. If a digraph D contains a path from a vertex x to a vertex y we say that y is reachable from x in D. In particular, x is reachable from itself. We denote by K∗a,b the complete bipartite digraph with partite sets of cardinalities a and b. 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. Two distinct vertices x and y are adjacent if xy ∈ A(D) or yx ∈ A(D) (or both). Let D be a bipartite digraph with partite sets X and Y . A matching from X to Y (from Y to X) is an independent set of arcs with origin in X and terminus in Y (origin in Y and terminus in X). (A set of arcs with no common end-vertices is called independent). If D is balanced, one says that such a matching is perfect if it consists of precisely |X| arcs. 3. Preliminaries In [21] and [11], the author studied pancyclicity of a digraph with the condition of the Meyniel theorem. Before stating the main result of [11] we need to define a family of digraphs. Definition 1: 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 is at least 2n − 1. 14 A Theorem on Even Pancyclic Bipartite Digraphs Theorem 12: (Darbinyan [11]). Let D be a strong 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 ei- ther (a) D is pancyclic or (b) n is even and D is isomorphic to one of digraphs K∗n/2,n/2, K∗n/2,n/2 \ {e}, where e is an arbitrary arc of K ∗ n/2,n/2, or (c) D ∈ Φ m n (in this case D does not contain only a cycle of length m). Later, Theorem 12, was also proved independently by Benhocine [22]. Lemma 2: (Adamus et al. [3]). Let D be a strong balanced bipartite digraph of order 2a ≥ 4 with partite sets X and Y . If d(x) + d(y) ≥ 3a for every pair of distinct vertices x, y from the same partite set, then D contains a perfect matching from Y to X and a perfect matching from X to Y . Following [15], we give the following definition. Definition 2: Let D be a balanced bipartite digraph of order 2a ≥ 4 with partite sets X and Y . Let My,x = {yixi ∈ A(D) | i = 1, 2, . . . , a} be a perfect matching from Y to X. We define a digraph D∗[My,x] with vertex set {v1, v2, . . . , va} as follows: each vertex vi corresponds to a pair {xi, yi} of vertices in D and for each pair of distinct vertices vl, vj, vlvj ∈ A(D∗[My,x]) if and only if xlyj ∈ A(D). Let D be a balanced bipartite digraph with partite sets X and Y . Let My,x be a perfect matching from Y to X in D and D∗[My,x] be its corresponding digraph. Further, in this paper, we will denote the vertices of D (respectively, of D∗[My,x]) by letters x, y (respectively, u, v) with subscripts or without them. The size of a perfect matching My,x = {yixi ∈ A(D) | i = 1, 2, . . . , a} from Y to X in D (denoted by s(My,x)) is the number of arcs yixi such that xiyi /∈ A(D). Using the arguments of [15] by Meszka, we can formulate the following lemma. Lemma 3: Let D be a balanced bipartite digraph of order 2a ≥ 6 with partite sets X and Y . Let My,x = {yixi ∈ A(D) | i = 1, 2, . . . , a} be a perfect matching from Y to X. Then the following hold: (i). d+(vi) = d +(xi) − −→a [xi, yi] and d−(vi) = d−(yi) − −→a [xi, yi]. (ii). If D∗[My,x] contains a cycle of length k, where k ∈ [2, a], then D contains a cycle of length 2k. (iii). Suppose that a is even, and D∗[My,x] is isomorphic to K ∗ a/2,a/2 with partite sets {v1, v2, . . . , va/2} and {va/2+1, va/2+2, . . . , va}. If D contains an arc from {y1, y2, . . . , ya/2} to {xa/2+1, xa/2+2, . . . , xa}, say ya/2xa ∈ A(D), then D contains a cycle of length 2k for all k = 2, 3, . . . , a. Proof. The proof of Lemma 3 can be found in [15], but we give it here for completeness. (i). It follows immediately from the definition of D∗[My,x]. (ii). Indeed, if vi1vi2 . . . vikvi1 is a cycle of length k in D ∗[My,x], then yi1xi1yi2xi2yi3 . . . yikxikyi1 is a cycle of length 2k in D. (iii). By (ii), it is clear that D contains cycles of every length 4k, k = 1, 2, . . . , a/2. It re- mains to show that D also contains cycles of every length 4k+2, k = 1, 2, . . . , a/2−1. Indeed, since xiyj ∈ A(D) and xjyi ∈ A(D) for all i ∈ [1, a/2], j ∈ [a/2 + 1, a] and ya/2xa ∈ A(D), S. Darbinyan 15 from the definition of D∗[My,x] it follows that y1x1ya/2+1xa/2+1y2x2ya/2+2xa/2+2y3 x3 . . . xkya/2+kxa/2+kya/2xay1 is a cycle of length 4k + 2 in D. Lemma 4: (Adamus [2]). Let D be a balanced bipartite digraph of order 2a ≥ 6 other than a directed cycle of length 2a. Suppose that d(x) + d(y) ≥ 3a for every good pair {x, y} of distinct vertices in D. Then d(u) ≥ a for all u ∈ V (D). Now let us prove Lemma 1. For convenience, we will restate it here. Lemma 1: Let D be a balanced bipartite digraph of order 2a ≥ 6 with partite sets X and Y . Suppose that D is not a directed cycle of length 2a and d(u) + d(v) ≥ 3a for every good pair of distinct vertices u, v. Then D either is even pancyclic or every pair of distinct vertices {x, y} from the same partite set is a good pair. Proof: Let X = {x1, x2, . . . , xa} and Y = {y1, y2, . . . , ya}. Suppose that V (D) contains a pair of vertices from the same partite set, which is not a good pair. Without loss of generality, assume that {x1, x2} is not a good pair. Then N+(x1) ∩ N+(x2) = N−(x1) ∩ N−(x2) = ∅, d+(x1) + d+(x2) ≤ a , d−(x1) + d−(x2) ≤ a. Hence, d(x1) + d(x2) ≤ 2a. This together with d(x1) ≥ a and d(x2) ≥ a (Lemma 4) implies that d(x1) = d(x2) = d +(x1) + d +(x2) = d −(x1) + d −(x2) = a. Now we obtain that N+(x1) ∪ N+(x2) = N−(x1) ∪ N−(x2) = Y . Let xi ∈ X \ {x1, x2} be an arbitrary vertex. We claim that {x1, xi} or {x2, xi} is a good pair. Assume that this is not the case. Then (N+(x1) ∪ N+(x2)) ∩ N+(xi) = ∅, which contradicts the facts that D is strong and N+(x1) ∪ N+(x2) = Y . Thus, {x1, xi} or {x2, xi} is a good pair for all i, 3 ≤ i ≤ a. Therefore, from condition (A) and d(x1) = d(x2) = a it follows that d(xi) = 2a for all i, 3 ≤ i ≤ a, i.e., D[X ∪ Y \ {x1, x2}] is a complete bipartite digraph with partite sets X \ {x1, x2} and Y . From d(x3) = 2a it follows that d +(x3) = d −(x3) = a. Therefore, if D contains a Hamiltonian cycle, then D contains cycles of all even lengths 2, 4, . . . , 2a. Now we will show that D contains a Hamiltonian cycle. Assume first that there is an (x1, x2)-path of length two. Let x1y1x2 be an (x1, x2)-path of length two. Then y1x1 /∈ A(D) and x2y1 /∈ A(D) as {x1, x2} is not a good pair. Now, since x2y1 /∈ A(D) and d+(x2) ≥ 1, we may assume that x2y2 ∈ A(D). From d−(x1)+d−(x2) = a ≥ 3 it follows that d−(x1) ≥ 2 or d−(x2) ≥ 2. Assume that d−(x1, {y3, y4, . . . , ya}) ≥ 1. We may assume that y3x1 ∈ A(D). Now using the fact that D[X ∪Y \{x1, x2}] is a complete bipartite digraph, we see that y3x1y1x2y2x3y4x4 . . . yaxay3 is a Hamiltonian cycle in D. Assume now that d−(x1, {y3, y4, . . . , ya}) = 0. Then from y1x1 /∈ A(D) and d−(x1) = 1 it follows that y2x1 ∈ A(D). Then x2y2x1 is an (x2, x1)-path of length two and d−(x2) ≥ 2. Now, we have that y2x2 /∈ A(D) since {x1, x2} is not a good pair. Therefore, d−(x2, {y3, y4, . . . , ya}) ≥ 1. Now, by repeating the above argument, we conclude that D is Hamiltonian. Similarly, one can show that if there is an (x2, x1)-path of length two, then again D is Hamiltonian. Assume next that there is no path of length two between x1 and x2. Then d−(x1, N +(x2)) = d −(x2, N +(x1)) = 0, and from N −(x1) ∪ N−(x2) = Y it follows that N−(x1) = N +(x1) and N −(x2) = N +(x2). This together with d(x1) = d(x2) = a implies that |N+(x1)| = |N+(x2)| = a/2, a is even and a ≥ 4. Without loss of generality, we assume that x1 ↔ {y1, y2} and x2 ↔ {ya−1, ya}. Now, since D[X ∪ Y \ {x1, x2}] is a complete 16 A Theorem on Even Pancyclic Bipartite Digraphs bipartite digraph, it is not difficult to check that x3y1x1y2x4y3x5y4 . . . xa−1ya−2xaya−1x2 yax3 is a Hamiltonian cycle in D. Thus, in all possible cases, D is Hamiltonian. Lemma 1 is proved. 4. Proof of the Main Result Let D be a strong balanced bipartite digraph of order 2a. We say that D satisfies condition (A) when d(x) + d(y) ≥ 3a for all distinct vertices x, y from the same partite set. The proof of Theorem 10 will be based on the following three lemmas below. Lemma 5: Let D be a strong balanced bipartite digraph of order 2a ≥ 6 with partite sets X and Y . If D satisfies condition (A), then D contains cycles of lengths 2 and 4. Proof: From condition (A) immediately follows that D contains a cycle of length 2. We will prove that D also contains a cycle of length 4. By Lemma 2, D contains a perfect matching from Y to X. Let My,x = {yixi ∈ A(D) | i = 1, 2, . . . , a} be a perfect matching from Y to X. If for some integers i, j, 1 ≤ i ̸= j ≤ a, the arcs xiyj, xjyi are in D, then xiyjxjyixi is a cycle of length 4. We may, therefore, assume that for every pair of integers i, j, 1 ≤ i ̸= j ≤ a, −→a [xi, yj] + −→a [xj, yi] ≤ 1. Therefore, for all i ∈ [1, a], d−(yi) ≤ a − d+(xi) − 1, if −→a [xi, yi] = 0 and d−(yi) ≤ a − d+(xi) + 1, if −→a [xi, yi] = 1. (1) Assume that there are two distinct integers i, j, 1 ≤ i, j ≤ a, such that −→a [xi, yi] = −→a [xj, yj] = 0. Then, by (1), d−(yi) + d+(xi) ≤ a − 1 and d−(yj) + d+(xj) ≤ a − 1. These together with condition (A) and the fact that the semi-degrees of every vertex in D are bounded above by a thus implies that 6a ≤ d(xi) + d(xj) + d(yi) + d(yj) = d−(yi) + d+(xi) + d−(yj) + d+(xj) +d+(yi) + d +(yj) + d −(xi) + d −(xj) ≤ 6a − 2, which is a contradiction. Assume now that for some i ∈ [1, a], −→a [xi, yi] = 0 and for all j ∈ [1, a]\{i}, −→a [xj, yj] = 1. Without loss of generality, we may assume that i = 1. By (1), d−(y1) + d +(x1) ≤ a − 1 and d−(y2)+d +(x2) ≤ a+1. If for some k ∈ [3, a], y2xk ∈ A(D) and ykx2 ∈ A(D), then x2y2xkykx2 is a cycle of length 4 in D. We may, therefore, assume that −→a [y2, xk] + −→a [yk, x2] ≤ 1 for all k ∈ [3, a]. This implies that d−(x2) + d +(y2) = d −(x2, {y1, y2}) + d+(y2, {x1, x2}) + d−(x2, Y \ {y1, y2}) +d+(y2, X \ {x1, x2}) ≤ 4 + a − 2 = a + 2. Using the above inequalities and condition (A), we obtain 6a ≤ d(x1) + d(x2) + d(y1) + d(y2) = d−(y1) + d+(x1) + d−(y2) + d+(x2) +d−(x2) + d +(y2) + d −(x1) + d +(y1) ≤ 5a + 2, which is a contradiction since a ≥ 3. S. Darbinyan 17 Assume finally that xiyi ∈ A(D) for all i ∈ [1, a]. In this case, by the symmetry between the vertices xi and yi, similar to (1), we obtain that d −(xi) + d +(yi) ≤ a + 1. This together with (1) implies that for any i, j (1 ≤ i ̸= j ≤ a), 6a ≤ d(xi) + d(xj) + d(yi) + d(yj) ≤ 4a + 4, a contradiction since a ≥ 3. Lemma 5 is proved. Remark 1: There is a strong balanced bipartite digraph of order 4, which satisfies condition (A), but contains no cycle of length 4. To see this, we consider the following digraph with vertex set V (D) = {x1, x2, y1, y2} and arc set D(A) = {x1y2, y2x2, x2y2, x2y1, y1x1}. Lemma 6: Let D be a strong balanced bipartite digraph of order 2a ≥ 6 with partite sets X and Y . Let My,x = {yixi ∈ A(D) | i = 1, 2, . . . , a} be a perfect matching from Y to X in D such that the size s(My,x) of My,x is maximum among the sizes of all the perfect matching from Y to X in D. If D satisfies condition (A), then the digraph D∗[My,x] either is strong or D contains cycles of all lengths 2, 4, . . . , 2a. Proof: Notice that, by Lemma 5, D contains cycles of lengths 2 and 4. Suppose that the digraph D∗[My,x] is not strong. Then in D ∗[My,x] there are two distinct vertices, say v1 and vj, such that there is no path from v1 to vj in D ∗[My,x]. Let U be the set of all vertices reachable from v1 and W be the set of all vertices from which vj is reachable. Notice that v1 ∈ U, vj ∈ W and U ∩ W = ∅. Case 1. d+(v1) ≥ 1 and d−(vj) ≥ 1. Then |U| ≥ 2 and |W| ≥ 2. Let vl, vk be two distinct vertices in U and vp, vq be two distinct vertices in W. From condition (A) and the fact that the semi-degrees of every vertex in D are bounded above by a it follows that d+(xl) + d +(xk) ≥ a and d−(xp) + d−(xq) ≥ a. (2) By Lemma 3(i), d+(vl) + d +(vk) = d +(xl) + d +(xk) − −→a [xl, yl] − −→a [xk, yk], and d−(vp) + d −(vq) = d −(yp) + d −(yq) − −→a [xp, yp] − −→a [xq, yq]. (3) It follows from them and (2) that d+(vl) + d +(vk) ≥ a − 2 and d−(vp) + d−(vq) ≥ a − 2. Without loss of generality we may assume that d+(vl) ≥ (d+(vl) + d+(vk))/2 and d−(vp) ≥ (d−(vp) + d −(vp))/2. These imply that d +(vl) ≥ (a − 2)/2 and d−(vp) ≥ (a − 2)/2, which in turn imply that |U| ≥ a/2 and |W| ≥ a/2. If d+(vl)+d +(vk) ≥ a−1 or d−(vp)+d−(vq) ≥ a−1, then |U| ≥ (a+1)/2 or |W| ≥ (a+1)/2, respectively. Hence |U| + |W| ≥ (2a + 1)/2, which is a contradiction since |U| + |W| ≤ a. Using (2) and (3), we may therefore assume that d+(vl) + d +(vk) = d +(xl) + d +(xk) − 2 = d−(vp) + d−(vq) = d−(yp) + d−(yq) − 2 = a − 2. 18 A Theorem on Even Pancyclic Bipartite Digraphs Then it is easy to see that the arcs xlyl, xkyk, xpyp and xqyq are in D, |U| = |W| = a/2 and V (D∗[My,x]) = U ∪ W . In particular, a is even. Without loss of generality, we assume that U = {v1, v2, . . . , va/2} and W = {va/2+1, va/2+2, . . . , va}. Since there is no arc from a vertex in U to a vertex in W, the following holds: A({x1, x2, . . . , xa/2} → {ya/2+1, ya/2+2, . . . , ya}) = ∅. (4) Therefore, if i ∈ [1, a/2] and j ∈ [a/2 + 1, a], then d+(xi) ≤ a/2 and d−(yj) ≤ a/2. Together with (2) they imply that d+(xi) = d −(yj) = a/2 and xi → {y1, y2, . . . , ya/2} and {xa/2+1, xa/2+2, . . . , xa} → yj (5) for all i ∈ [1, a/2] and j ∈ [a/2 + 1, a], respectively. Therefore, by condition (A), 3a ≤ d(xi) + d(xk) ≤ a + d−(xi) + d−(xk), for every pair of i, k ∈ [1, a/2]. This implies that d−(xi) = d−(xk) = a, which means that {y1, y2, . . . , ya} → {xi, xk}. Similarly, yj → {x1, x2 . . . , xa}, for all j ∈ [a/2 + 1, a]. From this and (5) it follows that the induced subdigraphs D[{x1, x2, . . . , xa/2, y1, y2, . . . , ya/2}] and D[{xa/2+1, xa/2+2, . . . , xa, ya/2+1, ya/2+2, . . . , ya}] both are balanced bipartite complete digraphs. Therefore, D contains cycles of all lengths 2, 4, . . . , a. It remains to show that D also contains cycles of every length a + 2b, b ∈ [1, a/2]. Since D is strong and (4), it follows that there is an arc from a vertex in {y1, y2, . . . , ya/2} to a vertex in {xa/2+1, xa/2+2, . . . , xa}. Without loss of generality, we may assume that ya/2xa/2+1 ∈ A(D). Then x1y1x2y2 . . . xa/2ya/2xa/2+1 ya/2+1xa/2+2 . . . xa/2+bya/2+bx1 is a cycle of length a + 2b. Thus, D contains cycles of all lengths 2, 4, . . . , 2a. This completes the discussion of Case 1. Case 2. d+(v1) = 0. Then d+(x1) = 1 and x1y1 ∈ A(D), since D is strong. Hence d(x1) ≤ a + 1. Together with condition A this implies that a ≤ d(x1) ≤ a + 1. We distinguish two subcases depending on d(x1). Case 2.1. d(x1) = a. Then d(xi) ≥ 2a for all i ∈ [2, a] because of condition A. Therefore, the induced subdigraph D⟨Y ∪X \{x1}⟩ is a complete bipartite digraph with partite sets Y and X \{x1}. It is clear that D contains cycles of every lengths 2, 4, . . . , 2a − 2. Since d(x1) = a, d+(x1) = 1 and a ≥ 3, we have that d−(x1) = a − 1 ≥ 2. Without loss of generality we may assume that y2x1 ∈ A(D). Then y2x1y1x3y3 . . . xayax2y2 is a cycle of length 2a. Case 2.2. d(x1) = a + 1. Then {y1, y2, . . . , ya} → x1 because of d+(x1) = 1, and, by condition (A), d(xi) ≥ 2a − 1 for all i ∈ [2, a]. Observe that if for some i ∈ [2, a], y1xi ∈ A(D), then Miy,x := {yix1, y1xi} ∪ {yjxj | j ∈ [1, a] \ {1, i}} is a perfect matching from Y to X in D. Assume that for some i ∈ [2, a], xiy1 /∈ A(D). Then y1xi ∈ A(D) because of d(xi) ≥ 2a−1. Since x1y1 ∈ A(D), xiy1 /∈ A(D) and x1yi /∈ A(D), it follows that s(Miy,x) > s(My,x), which contradicts the choice of My,x. We may therefore assume that {x2, x3, . . . , xa} → y1. If S. Darbinyan 19 y1xi ∈ A(D) and xiyi ∈ A(D), where i ∈ [2, a], then again we have s(Miy,x) > s(My,x), since the arcs x1y1, xiyi are in D and x1yi /∈ A(D). We may therefore assume that −→a [y1, xi] + −→a [xi, yi] ≤ 1. This together with d(xi) ≥ 2a − 1, i ∈ [2, a], implies that {y2, y3, . . . , ya} → xi → {y2, y3, . . . , ya} \ {yi}. (6) Since D is strong and d+(x1, {y2, y3, . . . , ya}) = 0, it follows that d+(y1, {x2, x3, . . . , xa}) ≥ 1. Without loss of generality, we assume that y1x2 ∈ A(D). Then, since y2x1 ∈ A(D) and (6), x1y1x2y3x3 . . . xk−1ykxky2x1 is a cycle of length 2k for every k ∈ [3, a]. Lemma 6 is proved. Lemma 7: Let D be a strong balanced bipartite digraph of order 2a ≥ 6 with partite sets X and Y . Let My,x = {yixi ∈ A(D) | i = 1, 2, . . . , a} be a perfect matching from Y to X in D such that the size s(My,x) of My,x is maximum among the sizes of all the perfect matching from Y to X in D. If D satisfies condition (A), then either d(u) + d(v) ≥ 2a − 1 for every pair of non-adjacent vertices u, v in D∗[My,x] or D contains cycles of all lengths 2, 4, . . . , 2a. Proof: Suppose that D is not even pancyclic. Then by Lemma 6, D∗[My,x] is strong. Let vi and vj be two arbitrary distinct vertices in D ∗[My,x]. Write g(i, j) := d+(xi) + d +(xj) + d −(yi) + d −(yj) and f(i, j) := d −(xi) + d −(xj) + d +(yi) + d +(yj). By Lemma 3(i), we have d(vi) + d(vj) = g(i, j) − 2−→a [xi, yi] − 2−→a [xj, yj]. (7) By condition (A), we have 6a ≤ d(xi) + d(xj) + d(yi) + d(yj) = f(i, j) + g(i, j). Hence, g(i, j) ≥ 2a and 4a ≥ f(i, j) ≥ 6a − g(i, j). (8) since the semi-degrees of every vertex of D are bounded above by a. Now we prove the following claim. Claim 1: Assume that the vertices vi and vj in D ∗[My,x] are not adjacent. Then the following hold: (i). If xiyi ∈ A(D) or xjyj ∈ A(D), then −→a [yi, xj] + −→a [yj, xi] ≤ 1. (ii). If xiyi /∈ A(D) or xjyj /∈ A(D), then d(vi) + d(vj) ≥ 2a − 1 in D∗[My,x]. Proof: Since the vertices vi and vj in D ∗[My,x] are not adjacent, it follows that xiyj /∈ A(D) and xjyi /∈ A(D). (i). Suppose, to the contrary, that xiyi ∈ A(D) or xjyj ∈ A(D), but −→a [yi, xj] + −→a [yj, xi] = 2. Then M ′y,x := {yixj, yjxi}∪{ykxk | k ∈ [1, a]\{i, j}} is a new perfect matching from Y to X in D. Since xjyi /∈ A(D), xiyj /∈ A(D) and xiyi ∈ A(D) or xjyj ∈ A(D), it follows that s(M ′y,x) > s(My,x), which contradicts the choice of My,x. (ii). If −→a [xi, yi] = −→a [xj, yj] = 0, then from (7) and g(i, j) ≥ 2a it follows that d(vi) + d(vj) ≥ 2a in D∗[My,x]. We may therefore assume that xiyi ∈ A(D). Then xjyj /∈ A(D) by the assumption of Claim 1(ii). If g(i, j) ≥ 2a+1, then, by (7), d(vi)+d(vj) ≥ 2a−1. 20 A Theorem on Even Pancyclic Bipartite Digraphs Thus, we may assume that g(i, j) = 2a. Then f(i, j) ≥ 4a by (8). The last inequality implies that the arcs yixj, yjxi are in D. Therefore, M ′ y,x := {yixj, yjxi}∪{ykxk | k ∈ [1, a]\{i, j}} is a new perfect matching from Y to X in D. Since xiyi ∈ A(D), xiyj /∈ A(D) and xjyi /∈ A(D), it follows that s(M ′y,x) > s(My,x), which contradicts the choice of My,x. The claim is proved. We now return to the proof of Lemma 7. Suppose that there exist two distinct non- adjacent vertices, say v1 and v2, in D ∗[My,x] such that d(v1) + d(v2) ≤ 2a − 2. (9) This together with (7), −→a [x1, y1] ≤ 1 and −→a [x2, y2] ≤ 1 implies that g(1, 2) ≤ 2a + 2. Therefore, 2a ≤ g(1, 2) ≤ 2a + 2. Case 1. −→a [x1, y1] = 0. Then from (7), (9) and the fact that g(1, 2) ≥ 2a, it follows that −→a [x2, y2] = 1 (i.e., x2y2 ∈ A(D)) and g(1, 2) = 2a. From this and (8) it follows that f(1, 2) ≥ 4a, which in turn implies that y1x2 ∈ A(D) and y2x1 ∈ A(D). The aforementioned contradicts Claim 1(i) since x2y2 ∈ A(D). Case 2. −→a [x1, y1] = −→a [x2, y2] = 1, i.e., x1y1 ∈ A(D) and x2y2 ∈ A(D). From Claim 1(i) it follows that y1x2 /∈ A(D) or y2x1 /∈ A(D). If 2a ≤ g(1, 2) ≤ 2a + 1, then from (8) it follows that f(1, 2) ≥ 4a − 1, which in turn implies that y1x2 ∈ A(D) and y2x1 ∈ A(D), which is a contradiction. We may therefore assume that g(1, 2) = 2a+2. This and (8) imply that f(1, 2) ≥ 4a−2. Then, since y1x2 /∈ A(D) or y2x1 /∈ A(D), it follows that y1x2 ∈ A(D) or y2x1 ∈ A(D). Without loss of generality, we may assume that y1x2 /∈ A(D) and y2x1 ∈ A(D). Note that the vertices y1 and x2 are not adjacent. Then f(1, 2) = 4a − 2, which in turn implies that d−(x1) = d +(y2) = a and d −(x2) = d +(y1) = a − 1. Therefore, y2 → {x1, x2, . . . , xa}; {y1, y2, . . . , ya} → x1; y1 → {x1, x3, x4, . . . , xa}; {y2, y3, . . . , ya} → x2. (10) since y1x2 /∈ A(D). Using (10), it is easy to see that for all i ∈ [3, a], Miy,x := {y2x1, yix2, y1xi} ∪ {ykxk | k ∈ [3, a] \ {i}} is a perfect matching from Y to X in D. Using the facts that the arcs x1y1, x2y2 are in D, it is not difficult to see that if for some i ∈ [3, a], either x2yi /∈ A(D) or xiy1 /∈ A(D) or xiyi ∈ A(D), then s(Miy,x) > s(My,x), which contradicts the choice of My,x. We may therefore as- sume that xiyi /∈ A(D) for all i ∈ [3, a], and x2 → {y2, y3, . . . , ya} and {x3, x4, . . . , xa} → y1. Together with (10) they imply that x2 ↔ {y2, y3, . . . , ya} and y1 ↔ {x1, x3, x4, . . . , xa}. (11) Since the vertices y1, x2 are not adjacent, from (11) and Lemma 3(i) it follows that d−(y1) = d +(x2) = a − 1, d−(v1) = d+(v2) = a − 2. (12) From g(1, 2) = 2a + 2, (7), x1y1 ∈ A(D) and x2y2 ∈ A(D) it follows that d(v1) + d(v2) = g(1, 2)−4 = 2a−2. This together with (12) and the fact that D∗[My,x] is strong implies that S. Darbinyan 21 d+(v1) = d −(v2) = 1. This means that d +(x1) = d −(y2) = 2. Therefore, d(x1) = d(y2) = a+2 by (10). Now for every i ∈ [3, a] we consider the perfect matching Miy,x and its corresponding digraph D∗[Miy,x]. Notice that s(My,x) = s(M i y,x) = a−2, the vertices y1, x2 are not adjacent and the arcs xiyi, x1y2 are not in A(D). Hence, the vertices v i 1 = {y1, xi}, vi2 = {yi, x2} in D∗[Miy,x] are not adjacent. From Claim 1(ii) it follows that in D ∗[Miy,x] the degree sum of every pair of two distinct non-adjacent vertices, other than {vi1, vi2}, is at least 2a − 1. If in D∗[Miy,x], d(v i 1) + d(v i 2) ≤ 2a − 2, then by the arguments to that in the proof of d(x1) = d(y2) = a + 2, we deduce that d(xi) = d(yi) = a + 2 for all i ∈ [3, a]. Therefore, for all i ∈ [3, a], 3a ≤ d(x1) + d(xi) ≤ 2a + 4. This means that a ≤ 4, i.e., a = 3 or a = 4. Let a = 3. By Lemma 5, it suffices to show that D contains a cycle of length 6. Using (10) and (11), it is easy to check that x3y2x2y3x1y1x3 is a cycle of length 6 in D. Let now a = 4. By Lemma 5, we need to show that D contains cycles of lengths 6 and 8. From d(x4) = 6 and x4y4 /∈ A(D) it follows that x4y2 ∈ A(D) or x4y3 ∈ A(D). Assume that x3y4 ∈ A(D). Then using (10) and (11) it is not difficult to see that x3y4x2y2x1y1x3 is a cycle of length 6, and x3y4x4y2x2y3x1y1x3 (respectively, x3y4x4y3x2y2 x1y1x3) is a cycle of length 8, when x4y2 ∈ A(D) (respectively, when x4y3 ∈ A(D)). Assume now that x3y4 /∈ A(D). Then from x4y4 /∈ A(D) and d(y4) = 6 it follows that x1y4 ∈ A(D). Now again using (10) and (11), we see that x1y4x2y2x3y1x1 is a cycle of length 6, and x1y4x4y2x2y3x3y1x1 (respectively, x1y4x4y3x2y2x3y1x1) is a cycle length 8, when x4y2 ∈ A(D) (respectively, when x4y3 ∈ A(D)). Thus, we have shown that if a = 3 or a = 4, then D contains cycles of all lengths 2, 4, . . . , 2a, which contradicts our supposition that D is not even pancyclic. This completes the proof of Lemma 7. We now ready to complete the proof of Theorem 10. Proof of Theorem 10: Let D be a digraph satisfying the conditions of Theorem 10. By Lemma 5, D contains cycles of lengths 2 and 4. By Lemma 2, D contains a perfect matching from Y to X. Let My,x = {yixi ∈ A(D) | i = 1, 2, . . . , a} be a perfect matching from Y to X in D with the maximum size among the sizes of all the perfect matching from Y to X in D. By Lemma 6, the digraph D∗[My,x] either contains cycles of all lengths 2, 4, . . . , 2a or is strongly connected. In the former case we are done. Assume that D∗[My,x] is strongly connected. By Lemma 7, D either contains cycles of all lengths 2, 4, . . . , 2a or (ii) d(u) + d(v) ≥ 2a − 1 for every pair of non-adjacent vertices u, v in D∗[My,x]. Assume that the second case holds. Therefore, by Theorem 12, either (a) D∗[My,x] contains cycles of every length k, k ∈ [3, a] or (b) a is even and D∗[My,x] is isomorphic to one of digraphs K ∗ a/2,a/2, K ∗ a/2,a/2 \ {e} or (c) D∗[My,x] ∈ Φma , where (a + 1)/2 < m ≤ a − 1. (a). In this case, by Lemma 5 and Lemma 3(ii), D contains cycles of every length 2k, k ∈ [1, a]. (b). D∗[My,x] is isomorphic to K ∗ a/2,a/2 or K ∗ a/2,a/2 \ {e} with partite sets {v1, v2, . . . , va/2} and {va/2+1, va/2+2, . . . , va}. Notice that a ≥ 4 and D∗[My,x] contains cycles of every length 2k, k ∈ [1, a/2]. Therefore, by Lemma 3(ii), D contains cycles of every length 4k, k ∈ [1, a/2]. It remains to show that for any k ∈ [1, a/2 − 1], D also contains a cycle of length 4k + 2. We claim that there exist p ∈ [1, a/2] and q ∈ [a/2+1, a] such that ypxq ∈ A(D). Assume that this is not the case, i.e., there is no arc from a vertex of {y1, y2, . . . , ya/2} to a vertex of {xa/2+1, xa/2+2, ldots, xa}. Then, since D∗[My,x] is isomorphic to K∗a/2,a/2 or K ∗ a/2,a/2 \ {e}, 22 A Theorem on Even Pancyclic Bipartite Digraphs from the definition of D∗[My,x] it follows that d +(y1) ≤ a/2, d+(ya/2) ≤ a/2, d−(y1) ≤ a/2+1 and d−(ya/2) ≤ a/2+1. Combining these inequalities, we obtain that d(y1)+d(ya/2) ≤ 2a+2, which contradicts condition (A) since a ≥ 4. It suffices to consider the case when D∗[My,x] is isomorphic to K ∗ a/2,a/2 \ {e}. Without loss of generality, we may assume that e = vava/2. From the definition of D ∗[My,x] it follows that {x1, x2, . . . , xa/2} → {ya/2+1, ya/2+2, . . . , ya} and D contains all possible arcs from {xa/2+1, xa/2+2, . . . , xa} to {y1, y2, . . . , ya/2} except xaya/2. If p = a/2 and q = a (i.e., ya/2xa ∈ A(D)), then y1x1ya/2+1xa/2+1y2x2ya/2+2xa/2+2 . . . ykxkya/2+k xa/2+kya/2xay1 is a cycle of length 4k + 2, where k ∈ [1, a/2 − 1]. Thus, we may assume that ya/2xa /∈ A(D). Then the vertices xa, ya/2 are not adjacent since xaya/2 /∈ A(D). This together with d−(ya/2, {x1, x2, . . . , xa/2}) ≤ 1 implies that d(ya/2) ≤ 3a/2 − 1. Therefore, by condition (A), d(ya/2−1) ≥ 3a/2 + 1 and hence, ya/2−1xa ∈ A(D) since d−(ya/2−1, {x1, x2, . . . , xa/2}) ≤ 1. Now it is not difficult to check that if a ≥ 6, then y1x1ya/2+1xa/2+1y2x2ya/2+2xa/2+2 . . . ykxkya/2+kxa/2+kya/2−1xay1 is a cycle of length 4k + 2 when k ∈ [1, a/2 − 2], and y1x1ya/2+1xa/2+1y2x2 ya/2+2xa/2+2 . . . xa/2−2ya−2xa−2ya/2xa/2 ya−1xa−1ya/2−1 xay1 is a cycle of length 2a − 2. If a = 4, then y2x2y4x4y1x3y2 is a cycle of length 6 = 2a − 2. (c). D∗[My,x] ∈ Φma . Since D contains cycles of lengths 2, 4 (Lemma 5) and every digraph in Φma is Hamiltonian, we can assume that a ≥ 4. Let V (D∗[My,x]) = {v1, v2, . . . , va} and vava−1 . . . v2v1va be a Hamiltonian cycle in D ∗[My,x]. Therefore, by the definition of D ∗[My,x], for all i ∈ [2, a], xiyi−1 ∈ A(D) and x1ya ∈ A(D). From the definition of Φma we have d+(va) = 1 and d +(va−1) ≤ 2. This means that d+(xa) ≤ 2 and d+(xa−1) ≤ 3. These together with d−(xa) ≤ a, d−(xa−1) ≤ a and condition (A) implies that d(xa) ≤ a + 2, d(xa−1) ≤ a + 3 and 3a ≤ d(xa) + d(xa−1) ≤ 2a + 5. (13) The last inequality of (13) implies that a ≤ 5, i.e., a = 4 or a = 5. Let a = 5. Then from (13) it follows that d(xa) + d(xa−1) = 2a + 5, d −(xa) = d−(xa−1) = a, i.e., {y1, y2, . . . , ya} → {xa, xa−1}. Therefore, y2x5y4x4y3x3y2 (respectively, y1x5y4x4y3x3y2x2y1) is a cycle of length 6 (respectively, of length 8). Let a = 4. In this case, we need to show that D contains a cycle of length 6. If x1y3 ∈ A(D) (or y2x1 ∈ A(D)), then x1y3x3y2x2y1x1 (respectively, x1y4x4y3x3y2x1) is a cycle of length 6. We may therefore assume that x1y3 /∈ A(D) and y2x1 /∈ A(D). Then d(x1) = d(x4) = 6 since d(x4) ≤ a + 2, d+(xa) ≤ 2 and d(x1) + d(x4) ≥ 12. Therefore, d−(x4) = 4, which in turn implies that y1x4 ∈ A(D). Hence, y1x4y3x3y2x2y1 is a cycle of length 6. Thus, we have shown that if D∗[My,x] ∈ Φma , then a = 4 or a = 5 and D contains cycles of all lengths 2, 4, . . . , 2a. This completes the proof of the theorem. 5. Conclusion In the current article, we prove a Meyniel-type condition and a Bang-Jensen, Gutin and Li-type condition for a strong balanced bipartite digraph of order 2a ≥ 6 to have cycles of all even lengths less than equal to 2a. It is worth to noting that over the past three years, various authors have received a number of sufficient conditions for the existence of cycles with certain properties in bipartite digraphs. In particular, several sufficient conditions for a balanced bipartite digraph to be S. Darbinyan 23 Hamiltonian or be even pancyclic were obtained (see, e.g., [23] by Wang and Wu, [24] by Adamus, [25] by Wang, [26] by Wang et al.). A Hamiltonian path in a digraph D in which the initial vertex dominates the terminal vertex is called a Hamiltonian bypass in D. It was proved that a number of sufficient condi- tions for a digraph to be Hamiltonian is also sufficient for a digraph to contain a Hamiltonian bypass with some exceptions, which are characterized in [27], and the papers cited there. It is not difficult to show that, if a balanced bipartite digraph of order 2a ≥ 4 satisfies the conditions of Theorem 2(a) (or 2(b)), then D has a Hamiltonian bypass. In this regard, we believe that the the following conjecture is true. Conjecture 3: D be a strong balanced bipartite digraph of order 2a ≥ 6. If D satisfies the conditions one of Theorems 2, 5 and 7, then D contains a Hamiltonian bypass, with some exceptions. To conclude this section, we mention that Wang et al. [28] constructed an infinite family of counterexamples to Conjecture 2. Note that each of these counterexamples contains a vertex, which has degree equal to three. Thus, Conjecture 2 remains open for digraphs with the minimum degree is at least four and for k-strong digraphs, where k ≥ 2. References [1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, 2000. [2] J. Adamus, “A degree sum condition for hamiltonicity in balanced bipartite digraphs”, Graphs and Combinatorics, vol. 33, no. 1, pp. 43-51, 2017. [3] J. Adamus, L. Adamus and A. Yeo, “On the Meyniel condition for hamiltonicity in bipartite digraphs”, Discrete Mathematics and Theoretical Computer Science, vol. 16 no. 1, pp. 293-302, 2014. [4] J. Bang-Jensen, Y. Guo and A. Yeo, “A new sufficient condition for a digraph to be hamiltonian”, Discrete Applied Mathematics, vol. 95, pp. 61-72, 1999. [5] J. Bang-Jensen, G. Gutin and H. Li, “Sufficient conditions for a digraph to be hamilto- nian”, Journal of Graph Theory, vol. 22, no. 2, pp. 181-187, 1996. [6] J.-C. Bermond and C. Thomassen, “Cycles in digraphs - A survey”, Journal of Graph Theory, vol. 5, no. 1, pp. 1-43, 1981. [7] A. Ghouila-Houri, “Une condition suffisante d’existence d’un circuit hamiltonien”, Comptes Rendus de I’ Academie des Science Paris Ser. A-B, vol. 25, pp. 495-497, 1960. [8] G. Gutin, “Cycles and paths in semicomplete multipartite digraphs, theorems and al- gorithms: a survey”, Journal of Graph Theory, vol. 19, no. 4, pp. 481-505, 1995. [9] D. Kühn and D. Osthus, “A survey on Hamilton cycles in directed graphs”, European Journal of Combinatorics, vol. 33, no. 5, pp. 750-766, 2012. [10] M. Meyniel, “Une condition suffisante d’existence d’un circuit hamiltonien dans un graphe oriente”, Journal Combinatorial Theory Ser. B, vol. 14, pp. 137-147, 1973. 24 A Theorem on Even Pancyclic Bipartite Digraphs [11] S.Kh. Darbinyan, “Pancyclicity of digraphs with the Meyniel condition”, Studia Scien- tiarum Mathematicarum Hungarica, vol. 20, no. 1-4, pp. 97-117, 1985 (Ph.D. Thesis, Institute Mathematici Akad. Nauk BSSR, Minsk, 1981) (in Russian). [12] S.Kh. Darbinyan, “On the pancyclicity of digraphs with large semidegrees”, Akademy Nauk Armyan SSR Dokllady, vol. 83, no. 3, pp. 99-101, 1986 (arXiv: 1111.1841v1). [13] R. Häggkvist and C. Thomassen, “On pancyclic digraphs”, Journal Combinatorial The- ory Ser. B, vol. 20, no. 1, pp. 20-40, 1976. [14] C. Thomassen, “An Ore-type condition implying a digraph to be pancyclic”, Discrete Mathematics, vol. 19, pp. 85-92, 1977. [15] M. Meszka, “New sufficient conditions for bipancyclicity of balanced bipartite digraphs”, Discrete Mathematics, vol. 341, no. 11, pp. 3237-3240, 2018. [16] R. Wang, “A sufficient condition for a balanced bipartite digraph to be hamiltonian”, Discrete Mathematics and Theoretical Computer Science, vol. 19, no. 3, no. 11, 2017. [17] S.Kh. Darbinyan, “Sufficient conditions for hamiltonian cycles in bipartite digraphs”, Discrete Applied Mathematics, vol. 258, pp. 87-96, 2019. [18] S.Kh. Darbinyan, “Sufficient conditions for a balanced bipartite digraph to be even pancyclic”, Discrete Applied Mathematics, vol. 238, pp. 70-76, 2018. [19] J. Adamus, “A Meyniel-type condition for bipancyclicity in balanced bipartite di- graphs”, Graphs and Combinatorics, vol. 34, no. 4, pp. 703-709, 2018. [20] S.Kh. Darbinyan and I.A. Karapetyan, “A sufficient condition for pre-hamiltonian cycles in bipartite digraphs”, ”2017 Computer Science and Information Technologies (CSIT)”, Yerevan, doi:10.1109/CSITechnol. 2017.8312150, pp. 101-109, 2017. [21] S.Kh. Darbinyan, “On pancyclic digraphs”, Preprint of the Computing Center of Akademy Nauk Armyan. SSR, 21 pp.,1979. [22] A. Benhocine, “Pancyclism and Meyniel’s conditions”, Discrete Mathematics, vol. 58, pp. 113-120, 1986. [23] R. Wang and L. Wu, “A dominating pair condition for a balanced bipartite digraph to be hamiltonian” , Australas. J. Combin. vol. 77, no. 1, pp. 136-143, 2020. [24] J. Adamus, “On dominating pair degree conditions for hamiltonicity in balanced bipar- tite digraphs”, Discrete Mathematics, vol. 344, no.3, Article 112240, 2021. [25] R. Wang, “Extremal digraphs on Woodall-type condition for hamiltonian cycles in bal- anced bipartite digraphs”, Journal of Graph Theory, https://doi.org/10.1002/jgt.22649, 25 November, 2020. [26] R. Wang, L. Wu and W. Meng, “Extremal digraphs on Meyniel-type condition for hamiltonian cycles in balanced bipartite digraphs”, arXiv:1910.05542v1. [27] S.Kh. Darbinyan, “On hamiltonian bypasses with the condition of Y. Manous- sakis”, ”2015 Computer Science and Information Technologies (CSIT)” Yerevan, doi:10.1109/CSITtechnol.2015.7358250 pp. 53-63, 2015. [28] R. Wang, J. Chang and L. Wu, “A dominated pair condition for a digraph to be hamil- tonian”, Discrete Mathematics, vol. 343, no. 5, 111794, 2020. Submitted 03.12.2020, accepted 04.03.2021. S. Darbinyan 2 5 »áñ»Ù »ñÏÙ³ëÝÛ³ ÏáÕÙÝáñáßí³Í ·ñ³ýÝ»ñÇ ½áõÛ· ѳٳóÇÏÉÇÏáõÃÛ³Ý Ù³ëÇÝ ê³Ùí»É Ê. ¸³ñµÇÝÛ³Ý ÐÐ ¶²² ÆÝýáñÙ³ïÇϳÛÇ ¨ ³íïáÙ³ï³óÙ³Ý åñáµÉ»ÙÝ»ñÇ ÇÝëïÇïáõï e-mail: samdarbin@iiap.sci.am ²Ù÷á÷áõÙ Ü»ñϳ ³ß˳ï³ÝùáõÙ ³å³óáõóí»É ¿ Ñ»ï¨Û³É ûáñ»ÙÁ: »áñ»Ù: ¸Çóáõù D-Ý áõÅ»Õ Ï³å³Ïóí³Í 2 a ¸ 6 -·³·³Ã³ÝÇ »ñÏÙ³ëÝÛ³ Ñ³í³ ë³ñ³Ïßéí³Í ÏáÕÙÝáñáßí³Í ·ñ³ý ¿, ÇëÏ fx; yg-Á D ·ñ³ýÇ ·³·³ÃÝ»ñÇ ó³Ýϳó³Í å³ñïíáÕ Ï³Ù Ñ³ÕÃáÕ ½áõÛ· ¿: ºÃ» ï»ÕÇ áõÝÇ d ( x ) + d( y ) ¸ 3 a å³ÛÙ³ÝÁ, ³å³ D -Ý å³ñáõݳÏáõÙ 2 a-Çó ÷áùñ ϳ٠ѳí³ë³ñ ó³Ýϳó³Í ½áõÛ· »ñϳñáõÃÛ³Ý óÇÏÉ, µ³óÇ ³ÛÝ ¹»åùÇó, »ñµ D-Ý 2 a »ñϳñáõÃÛ³Ý óÇÏÉ ¿: Òåîðåìà î ÷åòíûõ ïàíöèêëè÷åñêèõ äâóäîëüíûõ îðãðàôàõ Ñàìâåë Õ. Äàðáèíÿí Èíñòèòóò ïðîáëåì èíôîðìàòèêè è àâòîìàòèçàöèè ÍÀÍ ÐÀ e-mail: samdarbin@iiap.sci.am Àííîòàöèÿ  íàñòîÿùåé ðàáîòå äîêàçàíà ñëåäóþùàÿ òåîðåìà: Òåîðåìà: Ïóñòü D åñòü ñèëüíî ñâÿçíûé 2 a ¸ 6 - âåðøèííûé áàëàíñèðîâàííûé äâóäîëüíûé îðãðàô. Ïðåäïîëîæèì, ÷òî äëÿ êàæäîé äîìèíèðóþùåé è êàæäîé äîìèíèðóìîé ïàðû fx; yg ðàçëè÷íûõ âåðøèí èìååò ìåñòî d( x ) + d( y ) ¸ 3 a. Òîãäà D ñîäåðæèò êîíòóð ëþáîé ÷åòíîé äëèíû 2 k, 0 · k · a , êðîìå ñëó÷àÿ êîêäà D êèé îðãðàô, ÷åòíûé ïàíöèêëè÷åñêèé îðãðàô. ´³Ý³ÉÇ µ³é»ñ` ÎáÕÙÝáñáßí³Í ·ñ³ý, ѳÙÇÉïáÝÛ³Ý óÇÏÉ, »ñÏÙ³ëÝÛ³ ÏáÕÙÝáñáßí³Í ·ñ³ý, ѳٳóÇÏÉÇÏ, ½áõÛ· ѳٳóÇÏÉÇÏ: ÿâëÿåòñÿ êîíòóðîì äëèíû 2 a. Êëþ÷åâûå ñëîâà: Îðãðàô, ãàìèëüòîíîâ öèêë, äâóäîëüíèé îðãðàô, ïàíöèêëè÷åñ- 01_Darbinyan_55_MPCS_55.pdf (p.1-16) 01.pdf (p.17)