TR-2001-14

Highly edge-connected detachments of graphs and digraphs

Alex Berg, Bill Jackson, Tibor Jordán

Published in:
Journal of Graph Theory 43 (2003) 67-77



Abstract

Let G=(V,E) be a graph or digraph and r:V \to Z+. An r-detachment of G is a graph H obtained by `splitting' each vertex v \in V into r(v) vertices. The vertices v1,...,vr(v) obtained by splitting v are called the pieces of v in H. Every edge uv \in E corresponds to an edge of H connecting some piece of u to some piece of v. Crispin Nash-Williams 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.


Bibtex entry:

@techreport{egres-01-14,
AUTHOR = {Berg, Alex and Jackson, Bill and Jord{\'a}n, Tibor},
TITLE = {Highly edge-connected detachments of graphs and digraphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2001},
NUMBER = {TR-2001-14}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!