×

Highly edge-connected detachments of graphs and digraphs. (English) Zbl 1014.05043

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 \(v_1,v_2,\dots,v_{r(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\). C. St. J. A. Nash-Williams [J. Lond. Math. Soc., II. Ser. 31, 17-29 (1985; Zbl 0574.05042)] gave necesary and sufficient conditions for a graph to have a \(k\)-edge-connected \(r\)-detachment, and also solved the version where the degrees of all the pieces are specified. In this paper, the authors solve the same problems for directed graphs, and give a simple and self-contained new proof for the undirected result.

MSC:

05C40 Connectivity
05C20 Directed graphs (digraphs), tournaments

Citations:

Zbl 0574.05042
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Frank, Augmenting graphs to meet edge-connectivity requirements, SIAM J Disc Math 5 pp 25– (1992) · Zbl 0782.05054
[2] Fleiner, Detachments of vertices of graphs preserving edge-connectivity, SIAM J Disc Math · Zbl 1069.05044
[3] Jackson, Non-separable detachments of graphs, J Combin Theory (B) · Zbl 1184.05106
[4] Jordán, Detachments preserving local edge-connectivity of graphs, SIAM J Disc Math. · Zbl 1038.05033
[5] Lovász, Combinatorial problems and exercises (1979)
[6] Mader, A reduction method for edge-connectivity in graphs, Annals of Discrete Math 3 pp 145– (1978) · Zbl 0389.05042
[7] Mader, Konstruktion aller n-fach kantenzusammenhängenden Digraphen, Eur J Combin 3 pp 63– (1982) · Zbl 0488.05037
[8] Nash-Williams, Lond Math Soc Lecture Note Ser 103 pp 137– (1985)
[9] Nash-Williams, Connected detachments of graphs and generalized Euler trails, J Lond Math Soc 31 pp 17– (1985) · Zbl 0574.05042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.