Non-zero disjoint cycles in highly connected group labelled graphs (Q2490257): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.jctb.2005.08.001 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1984537627 / rank | |||
Normal rank |
Revision as of 01:58, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Non-zero disjoint cycles in highly connected group labelled graphs |
scientific article |
Statements
Non-zero disjoint cycles in highly connected group labelled graphs (English)
0 references
28 April 2006
0 references
Let \(G\) be an oriented graph whose edges are labelled by elements of a group \(\Gamma\). A non-zero cycle in \(G\) is a cycle \(C\) of the underlying undirected graph \(G'\) such that for a given orientation of \(C\) adding the labels of the forward directed edges and subtracting the labels of the backward directed edges does not result in zero. Generalizing previous results due to Thomassen, Rautenbach and Reed, and Kawarabayashi and Reed, the authors prove that if \(G'\) is \((31/2)k\)-connected, then either \(G\) contains \(k\) disjoint non-zero cycles or there is a set \(Q\) of at most \(2k-2\) vertices such that \(G-Q\) has no non-zero cycle.
0 references
Erdős-Pósa property
0 references
group labelled graph
0 references
non-zero cycle
0 references