Non-zero disjoint cycles in highly connected group labelled graphs (Q2490257)
From MaRDI portal
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