Highly edge‐connected detachments of graphs and digraphs
Alex R. Berg, Bill Jackson, Tibor Jordán · Journal of Graph Theory · 2003
Abstract Let G = ( V , E ) be a graph or digraph and r : V → Z + . An r ‐detachment of G is a graph H obtained by ‘splitting’ each vertex ν ∈ V into r (ν) vertices. The vertices ν 1 ,…,ν r (ν) obtained by splitting ν are called the pieces of ν in H . Every edge u ν ∈ E corresponds to an edge of H connecting some piece of u to some piece of ν. Crispin Nash‐Williams 9 gave necessary and sufficient conditions for a graph to have a k ‐edge‐connected r ‐detachment. He also solved the version where the degrees of all the pieces are specified. In this paper, we solve the same problems for directed graphs. We also give a simple and self‐contained new proof for the undirected result. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 67–77, 2003