Highly edge-connected detachments of graphs and digraphs.

*(English)*Zbl 1014.05043Let \(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.

Reviewer: Jun-Ming Xu (Hefei)

PDF
BibTeX
XML
Cite

\textit{A. R. Berg} et al., J. Graph Theory 43, No. 1, 67--77 (2003; Zbl 1014.05043)

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.