Premium
Edge disjoint cycles through specified vertices
Author(s) -
Goddyn Luis,
Stacho Ladislav
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20104
Subject(s) - combinatorics , mathematics , disjoint sets , lemma (botany) , bipartite graph , discrete mathematics , graph , pairwise comparison , bound graph , graph factorization , simple graph , graph power , line graph , ecology , statistics , poaceae , biology
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 2 k ‐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 2 k 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