Extending cycles in bipartite graphs

AbstractLet 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) ⊆ 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 bipan-cyclic ordering if the vertices of X and Y can be labelled x1, x2, …, xn and y1, y2, …, yn, respectively, so that C2k ⊆ 〈x1, …, xk, y1, …, yk〉, for 2≦k≦n. Let ρ(G)=min{d(x)+d(y):xϵX, yϵY,andxy∉E(G)}.It is shown that if σ(G) ≧ n + 1 and C is a 2k-cycle in G then C is extendable unless 〈V(C)〉 ≅ Kk, k. As consequences of the proof of this result, we deduce that if either σ(G) ≧ (7n + 1)6 or δ(G) ≧ (n + 1)2 then, in each case with one exceptional graph, G is bi-cycle extendable. It is also shown that if l is an integer such that n≧2l≧2, δ(G) ≧ l, and |E(G)| ≧ n2 − ln + l2 then every cycle of length at least l in G is extendable unless G≅Kn, n − E(Kl, n−l). As a corollary, we deduce that such a graph G has a bipancyclic ordering unless G≅Kn, n − E(Kl, n−l). 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