Extending cycles in bipartite graphs (Q1121281)

Let G(X,Y,E) be a balanced bipartite graph of order 2n. We introduce the following definitions. A cycle C in G is extendable if there exists a cycle C' in G such that V(C)\(\subseteq V(C')\) and \(| V(C')| =| V(C)| +2\). G is bi-cycle extendable if G has at least one cycle and every nonhamiltonian cycle in G is extendable. G has a bi- pancyclic ordering if the vertices of X and Y can be labelled \(x_ 1,x_ 2,...,x_ n\) and \(y_ 1,y_ 2,...,y_ n\), respectively, so that \(C_{2k}\subseteq <x_ 1,...,x_ k,y_ 1,...,y_ k>,\) for \(2\leq k\leq n.\) Let \[ {\bar \sigma}(G)=\min \{d(x)+d(y):\quad x\in X,\quad y\in Y\quad and\quad xy\not\in E(G)\}. \] It is shown that if \({\bar \sigma}\)(G)\(\geq n+1\) and C is a 2k-cycle in G then C is extendable unless \(<V(C)>\cong K_{k,k}\). As consequences of the proof of this result, we deduce that if either \({\bar \sigma}(G)\geq (7n+1)/6\) or \(\delta (G)\geq (n+1)/2\) then, in each case with one exceptional graph, G is bi-cycle extendable. It is also shown that if \(\ell\) is an integer such that \(n\geq 2\ell \geq 2,\) \(\delta (G)\geq \ell\) and \(| E(G)| \geq n^ 2-\ell n+\ell^ 2\) then every cycle of length at least \(\ell\) in G is extendable unless \(G\cong K_{n,n}-E(K_{\ell,n-\ell}).\) As a corollary, we deduce that such graph G has a bi-pancyclic ordering unless \(G\cong K_{n,n}-E(K_{\ell,n-\ell}).\) A number of preliminary results are required, among which is the determination of the maximum size of a balanced bipartite graph of specified order, minimum degree and edge independence number.