×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: DOI EuDML