Packing directed cycles through a specified vertex set

KAWARABAYASHI, K; Daniel KRÁĽ; M KRCAL a S KREUTZER. Packing directed cycles through a specified vertex set. PHILADELPHIA: SIAM, 2013, s. 365-377.

Základní údaje

Originální název

Packing directed cycles through a specified vertex set

Autoři

KAWARABAYASHI, K; Daniel KRÁĽ; M KRCAL a S KREUTZER

Vydání

PHILADELPHIA, SIAM, 2013

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

UT WoS

000461897900027

---

Anotace

V originále

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.