TR-2001-12

Non-separable detachments of graphs

Bill Jackson, Tibor Jordán

Published in:
J. Comb Theory B 87 (2003) 17-37.



Abstract

Let G=(V,E) be a graph and r: V \rightarrow Z+. An r-detachment of G is a graph H obtained by `splitting' each vertex v \in V into r(v) vertices, 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. An r-degree specification for G is a function f on V, such that, for each vertex v \in V, f(v) is a partition of d(v) into r(v) positive integers. An f-detachment of G is an r-detachment H in which the degrees in H of the pieces of each v \in V are given by f(v). Crispin Nash-Williams obtained necessary and sufficient conditions for a graph to have a k-edge-connected r-detachment or f-detachment. We solve a problem posed by Nash-Williams by obtaining analogous results for non-separable detachments of graphs.


Bibtex entry:

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


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