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 + τ(F), where τ(F) = ⌈k/2⌉ + ɛ (here ɛ = 1 if t1 = 0 or if (t1, t2)∈{(1, 0), (2, 0)}, and ɛ = 0 otherwise). We show also that this threshold on the degree-sum is sharp when n>3k. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:1–17, 2012 © 2012 Wiley Periodicals, Inc.
['Reza Zamani', 'Douglas B. West']
Spanning Cycles Through Specified Edges in Bipartite Graphs