Hamiltonian Cycles and Hamiltonian-biconnectedness
Ciclos Hamiltonianos, Denise Amar, Daniel Brito · 2006
Let D denote a balanced bipartite digraph with 2n vertices and for each vertex x, d + (x) ‚ k, d i (x) ‚ k, k ‚ 1, such that the maximum cardinality of a balanced independent set is 2fl and n = 2fl + k. We give two functions F(n;fl) and G(n;fl) such that if D has at least F(n;fl) (resp. G(n;fl)) arcs, then it is hamiltonian (resp. hamiltonianbiconnected).