PascalGollin

Given a cardinal $\lambda$, a $\lambda$-packing of a graph $G$ is a family of $\lambda$ many edge-disjoint spanning trees of $G$, and a $\lambda$-covering of $G$ is a family of spanning trees covering $E(G)$.We show that if a graph admits a $\lambda$-packing and a $\lambda$-covering  then the graph also admits a decomposition into $\lambda$ many spanning …

A dibond in a directed graph is a bond (i.e. a minimal non-empty cut) for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of an edge set meeting every dicut equals the maximum …

A rooted digraph is a vertex-flame if for every vertex v there is a set of internally disjoint directed paths from the root to v whose set of terminal edges covers all ingoing edges of v. It was shown by Lovász that every finite rooted digraph admits a spanning subdigraph which is a vertex-flame and large, where the latter means …

Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. We therefore say that cycles satisfy the Erdős-Pósa property. However, while odd cycles do not satisfy the Erdős-Pósa property, Reed proved in 1999 an analogue by …