Spanning Cycles Through Specified Edges in Bipartite Graphs

Posa proved that if G is an n-vertex graph in which any two nonadjacent vertices have degree-sum at least n + k, then G has a spanning cycle containing any specified family of disjoint paths with a total of k edges. We consider the analogous problem for a bipartite graph G with n vertices and parts of equal size. Let F be a subgraph of G whose components are nontrivial paths. Let k be the number of edges in F, and let t1 and t2 be the numbers of components of F having odd and even length, respectively. We prove that G has a spanning cycle containing F if any two nonadjacent vertices in opposite partite sets have degree-sum at least n/2 + tau(F), where tau(F) = tau k/2? + epsilon (here epsilon = 1 if t1 = 0 or if (t1, t2)epsilon{(1, 0), (2, 0)}, and epsilon = 0 otherwise). We show also that this threshold on the degree-sum is sharp when n>3k. (c) 2011 Wiley Periodicals, Inc. J Graph Theory 71:117, 2012