Title:

Sufficient conditions for a balanced bipartite digraph to be even pancyclic

Author:

Darbinyan Samvel

Type:

Article

Uncontrolled Keywords:

Digraphs ; Cycles ; Hamiltonian cycles ; Bipartite balanced digraph ; Pancyclic ; Even pancyclic ; Longest non-Hamiltonian cycles

Abstract:

Let D be a strongly connected balanced bipartite directed graph of order 2a≥8. In this note we prove: (i). If D contains a cycle of length 2a−2≥6 and max{d(x),d(y)}≥2a−2 for every pair of vertices {x,y}with a common out-neighbour, then for every k, 1≤k≤a−1, D contains a cycle of length 2k. (ii). If D is not a directed cycle and max{d(x),d(y)}≥2a−1 for every pair of vertices {x,y} with a common out-neighbour, then for every k, 1≤k≤a, D contains a cycle of length 2k unless D is isomorphic to a certain digraph of order eight which we specify.

Publisher:

Elsevier

Date submitted:

28.03.2017

Date accepted:

08.12.2017

Date of publication:

05.01.2018

DOI:

10.1016/j.dam.2017.12.013

ISSN:

0166-218X

Language:

English

Journal or Publication Title:

Discrete Applied Mathematics

Volume:

238

URL:


Additional Information:

samdarbin@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems

Country:

Armenia

Indexing:

WOS