Informace o publikaci
Packing directed cycles through a specified vertex set
| Autoři | |
|---|---|
| Rok publikování | 2013 |
| Druh | Článek v odborném periodiku |
| Citace | |
| Popis | A seminal result of Reed et al. [15] in 1996 states that the Erdos-Posa property holds for directed cycles, i.e. for every integer n there is an integer t such that every directed graph G has n pairwise vertex disjoint directed cycles or contains a set T subset of V (G) of at most t vertices such that G-T contains no directed cycle. In this paper, we consider the Erdos-Posa property for directed cycles through a vertex in a given vertex set S, i.e. the question if for every integer n there is an integer t such that if G is a directed graph G and S is a set of vertices then G has n pairwise vertex disjoint directed cycles each containing a vertex of S or contains a set T of at most t vertices such that G-T contains no such directed cycle. For undirected graphs, this property holds for cycles through a vertex in a vertex set S (see Kakimura, Kawarabayashi and Marx [9], and Pontecorvi and Wollan [12]). In this paper, we show the following: The Erdos-Posa does hold for half-integral packings of directed cycles each containing a vertex from S, i.e. where every vertex of the graph is contained in at most 2 cycles. On the other hand, an example shows that the Erdos-Posa property does not hold without this relaxation. |