Article ID Journal Published Year Pages File Type
4657431 Journal of Combinatorial Theory, Series B 2006 6 Pages PDF
Abstract

Let G=(V,E) be an oriented graph whose edges are labelled by the elements of a group Γ. 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 Γ-labelled graph and is the corresponding undirected graph, then if is -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 Erdős–Pósa property for odd cycles in graphs with large connectivity, Combinatorica 21 (2001) 321–333.), Rautenbach and Reed (The Erdős–Pósa property for odd cycles in highly connected graphs, Combinatorica 21 (2001) 267–278.) and Kawarabayashi and Reed (Highly parity linked graphs, preprint.), respectively.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics