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.
oai:noad.sci.am:136254
Mathematical Problems of Computer Science
Institute for Informatics and Automation Problems of NAS RA
Jan 25, 2022
Jan 25, 2022
23
https://noad.sci.am/publication/149819
Edition name | Date |
---|---|
Samvel Kh. Darbinyan, A Theorem on Even Pancyclic Bipartite Digraphs | Jan 25, 2022 |
Darbinyan Samvel Kh.