AN ALGORITHM FOR FINDING LONGEST CYCLES IN CERTAIN BIPARTITE GRAPHS

Let G be a connected bipartite graph with with bipartition (X, Y) such that |X| ≥ |Y| (≥ 2). Put n = |X|, m = |Y| and l = m + n. Suppose that, for all vertices x ∈ X and y ∈ Y, dist(x,y) = 3 implies d(x) + d(y) ≥ n + 1. We show that G contains a cycle of length 2m. We also give an efficient algorithm to obtain such a cycle. The complexity of this algorithm is O(l³). In case m = n, we find a hamiltonian cycle of G. This generalizes a result given in [10].