Packing cycles with modularity constraints (Q653988): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:52, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Packing cycles with modularity constraints |
scientific article |
Statements
Packing cycles with modularity constraints (English)
0 references
20 December 2011
0 references
Let \(G\) be a graph and let \(\Gamma\) be an Abelian group with no element of order two. Let \(\gamma:E(G)\to \Gamma\) be a function from the edges of \(G\) to the elements of \(\Gamma\). A non-zero cycle is a cycle \(C\) such that \(\sum_{e\in E(G)}\gamma(e) \not= 0\) where \(0\) is the identity element of \(\Gamma\). Then \(G\) either contains \(k\) vertex disjoint non-zero cycles or there exists a set \(X\subseteq V(G)\) with \(| X| \leq N(k)\) such that \(G-X\) contains no non-zero cycle, where \(N(k)\) is an integer depending on \(k\). An immediate consequence is that for all positive odd integers \(m\), a graph \(G\) either contains \(k\) vertex disjoint cycles of length not congruent to \(0 \mod m\), or there exists a set \(X\) of vertices with \(| X| \leq N(k)\) such that every cycle of \(G-X\) has length congruent to \(0 \mod m\). No such value \(N(k)\) exists when \(m\) is allowed to be even, as examples of \textit{B. Reed} [Combinatorica 19, 267--296 (1999; Zbl 0928.05059)] and \textit{C. Thomassen} [J. Graph Theory 12, 101--111 (1988; Zbl 0662.05032)] show.
0 references
disjoint cycles
0 references
Abelian group
0 references
Erdős-Pósa property
0 references
packing
0 references
modularity constraints
0 references