کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657431 1343737 2006 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Non-zero disjoint cycles in highly connected group labelled graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Non-zero disjoint cycles in highly connected group labelled graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 96, Issue 2, March 2006, Pages 296-301