On long cycles in a 2-connected bipartite graph (Q2563427): Difference between revisions

A result of Bermond states that for a 2-connected graph \(G\) on \(n\) vertices and integer \(k\geq 3\), if \(d(x)+d(y)\geq k\) for every pair of non-adjacent vertices \(x\) and \(y\) of \(G\) then \(G\) contains a cycle of length \(\geq\min(k,n)\). The author shows a similar result for 2-connected bipartite graphs \(G=(A,B;E)\): For \(k\) any integer \(\geq 2\), if \(d(x)+d(y)\geq k+1\) for each pair of non-adjacent vertices \(x\) and \(y\) then \(G\) contains a cycle of length \(\geq\min(2a,2k)\) where \(a=\min(|A|,|B|)\), unless \(G\) is a member of a known family. The author conjectures the result is true when \(|A|=|B|\) and the degree condition is restricted to vertex pairs \(x\), \(y\) with \(x\in A\) and \(y\in B\).