| Abstract: | We give a sufficient condition for a simple graph G to have k pairwise edge‐disjoint cycles, each of which contains a prescribed set W of vertices. The condition is that the induced subgraph G[W] be 2k‐connected, and that for any two vertices at distance two in G[W], at least one of the two has degree at least |V(G)|/2 + 2(k ? 1) in G. This is a common generalization of special cases previously obtained by Bollobás/Brightwell (where k = 1) and Li (where W = V(G)). A key lemma is of independent interest. Let G be the complement of a bipartite graph with partite sets X, Y. If G is 2k connected, then G contains k Hamilton cycles that are pairwise edge‐disjoint except for edges in G[Y]. © 2005 Wiley Periodicals, Inc. J Graph Theory |
