Let G=(V,E) be an oriented graph whose edges are labelled by the elements of a group Gamma. A cycle C in G has non-zero weight if for a given orientation of the cycle, when we add the labels of the forward directed edges and subtract the labels of the reverse directed edges, the total is non-zero. We are specifically interested in the maximum number of vertex disjoint non-zero cycles. We prove that if G is a Gamma-labelled graph and (G) over bar is the corresponding undirected graph, then if (G) over bar is 31/2k-connected, either G has k disjoint non-zero cycles or it has a vertex set Q of order at most 2k-2 such that G-Q has no non-zero cycles. The bound "2k-2" is best possible. This generalizes the results due to Thomassen (The Erdos-Posa property for odd cycles in graphs with large connectivity, Combinatorica 21 (2001) 321-333.), Rautenbach and Reed (The Erdos-Posa property for odd cycles in highly connected graphs, Combinatorica 21 (2001) 267-278.) and Kawarabayashi and Reed (Highly parity linked graphs, preprint.), respectively. (C) 2005 Elsevier Inc. All rights reserved.
Non-zero disjoint cycles in highly connected group labelled graphs / Ken Ichi, Kawarabayashi; Wollan, PAUL JOSEPH. - In: JOURNAL OF COMBINATORIAL THEORY. - ISSN 0095-8956. - 96:2(2006), pp. 296-301.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
|Titolo:||Non-zero disjoint cycles in highly connected group labelled graphs|
|Data di pubblicazione:||2006|
|Citazione:||Non-zero disjoint cycles in highly connected group labelled graphs / Ken Ichi, Kawarabayashi; Wollan, PAUL JOSEPH. - In: JOURNAL OF COMBINATORIAL THEORY. - ISSN 0095-8956. - 96:2(2006), pp. 296-301.|
|Appartiene alla tipologia:||01a Articolo in rivista|