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.

Date of publication:

2021-12-16

Identifier:

oai:noad.sci.am:136254

DOI:

10.51408/1963-0069

Other identifier:

UDC 519.1

Language:

English

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

55

URL:

Affiliation:

Institute for Informatics and Automation Problems of NAS RA

Country:

Armenia

Year:

2021