## Longest cycles in certain bipartite graphs.(English)Zbl 0890.05040

For a connected bipartite graph with bipartition $$(X,Y)$$, where $$|X|= n \geq m = |Y|\geq 2$$, the condition “dist$$(x,y) = 3$$, $$x \in X$$, $$y \in Y$$ implies $$d(x) + d(y) \geq n+1$$” ensures that a cycle of length $$2m$$ exists. The graph is Hamiltonian if $$m=n$$.

### MSC:

 05C38 Paths and cycles 05C45 Eulerian and Hamiltonian graphs

### Keywords:

bipartite graph; Hamiltonian graph; bipartition; cycle
Full Text: