On the bipartite independence number of a balanced bipartite graph (Q1309450): Difference between revisions

The bipartite independence number \(\alpha_{\text{BIP}} (G)\) of a bipartite graph \(G\) is the maximum cardinality of a balanced independent set. \textit{P. Ash} [Ars Comb. 16 A, 33-37 (1983; Zbl 0534.05041)] proved that if the balanced bipartite graph \(G\) is 2-connected, \(n \leq 3 \delta- 3\) and \(\alpha_{\text{BIP}} (G)<(2\delta-3)/3\), then \(G\) is hamiltonian. \textit{Fraisse} [\(D_ \lambda\)-cycles and their applications for hamiltonian graphs, Thesis, Université Paris-Sud, 1986] showed that every 2-connected balanced bipartite graph for which \(\alpha_{\text{BIP}} \leq \delta-1\) is hamiltonian. \textit{O. Favaron} et al. [SIAM J. Discrete Math. 6, 189-196 (1993)] dropped the connectedness condition in showing that if the balanced bipartite graph \(G\) satisfies \(\alpha_{\text{BIP}} \leq 2 \leq \delta\) then, with two exceptional graphs, \(G\) is hamiltonian. Among other results the authors prove the following. If \(G\) is a balanced bipartite graph of minimum degree \(\delta \geq 1\) and there exists an integer \(t\), \(0 \leq t \leq \delta-1\) such that \(\alpha_{\text{BIP}} \leq \delta+t\), then \(G\) is \((\delta-t)\)- connected. If the balanced bipartite graph \(G\) satisfies \(\alpha_{\text{BIP}} \leq \delta\), then, with two exceptional graphs, \(G\) is hamiltonian.