Title:
A Theorem on Even Pancyclic Bipartite Digraphs
Author:
Type:
Uncontrolled Keywords:
Digraphs ; Hamiltonian cycles ; Bipartite digraphs ; Pancyclic ; Even pancyclic
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:
DOI:
Other identifier:
Language:
Journal or Publication Title:
Mathematical Problems of Computer Science
Volume:
URL:
Affiliation:
Institute for Informatics and Automation Problems of NAS RA