Neighborhood conditions for balanced independent sets in bipartite graphs (Q1381845): Difference between revisions

Let us assume that \(\Gamma\) is a balanced bipartite graph (i.e., \(\Gamma\) admits a bipartition into two independent vertex sets with the same cardinality) of order \(2n\) in which all valences are \(\geq3\). We assume further that the neighborhood \(N(S)\) of any independent 4-subset \(S\) of \(V(\Gamma)\) consisting of two vertices from each side of the bipartition satisfies \(|N(S)|>n\). In this clearly-written, well-motivated, example-rich paper, the following conclusions are deduced: \(\Gamma\) is either Hamiltonian or contains a spanning subgraph consisting of a cycle and an isolated edge; \(\Gamma\) is traceable; \(\Gamma\) either has a 2-factor or belongs to a small subclass of examples in which \(n=7\). It is conjectured that under the above assumptions, \(\Gamma\) is Hamiltonian or belongs to this small subclass. By sharpening the inequality to \(|N(S)|>n+2\), the authors show that \(\Gamma\) is in fact Hamiltonian.