Hamiltonian properties and the bipartite independence number Original Research Article

By using the notion of compatibility of subgraphs with a perfect matching developed for diagraphs in [1], we show that if, in a balanced bipartite graph G of minimum degree δ, the maximum cardinality αbip of a balanced independent subset satisfies αbip ⩽ 2δ - 4, then G is hamiltonian-biconnected, and if αbip ⩽ 2δ - 2, G contains a hamiltonian path. Moreover, we give some properties of balanced bipartite graphs which are not hamiltonian, and which satisfy αbip ⩽ 2δ - 2.