Detachments Preserving Local Edge-Connectivity of Graphs

DOI10.1137/S0895480199363933MaRDI QIDQ4443122zbMATH OpenOpenAlexFDO

Authors Zoltán Szigeti, Tibor Jordán

Publication date 8 January 2004

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480199363933

zbMATH Keywords

degree-specification detachments of graphs edge-splitting

Mathematics Subject Classification ID

Connectivity (05C40) Combinatorial optimization (90C27)

Review text

Let \(G=(W,E)\) be a loopless undirected multigraph, and let \(s\in W\). Let \(f(s)=(d_1,\ldots,d_p)\) be a sequence of positive integers whose sum is the valence of \(s\); \(f(s)\) is called a degree specification. An \(f(s)\)-detachment of \(G\) is a multigraph \(G'=((W\backslash\{s\})\cup\{s_1,\ldots,s_p\},E')\) obtained by ``splitting \(s\) into the \(p\) vertices \(s_1,\ldots,s_p\) so that \(s_i\) has valence \(d_i\) in \(G'\) (\(1\leq i\leq p\)) and each edge \(st\in E\) corresponds to some edge \(s_it\in E'\). For \(U\subseteq W\), a function \(r:{\mathcal P}_2(U)\to Z^+\) is called a requirement function on \(U\); \(G\) is said to be \(r\)-edge connected in \(U\) if for all \(\{x,y\}\in{\mathcal P}_2(U)\) the maximum number of pairwise edge-disjoint \(xy\)-paths in \(G\) is at least \(r(x,y)\). The main result is the following. Theorem: Let \(G=(W,E)\) be a loopless multigraph with a designated vertex \(s\in W\) incident with no cut-edge. Let a degree specification \(f(s)=(d_1,\ldots,d_p)\) such that all \(d_i\geq2\) and a requirement function \(r\) on \(W\backslash\{s\}\) be given. Then there exists an \(f(s)\)-detachment of \(G\) which is \(r\)-edge connected in \(W\backslash\{s\}\) if and only if (1) \(G\) is \(r\)-edge connected in \(W\backslash\{s\}\) and (2) for all 2-sets \(\{x,y\}\) of vertices in \(G-s\) the maximum number of pairwise edge-disjoint \(xy\)-paths in \(G-s\) is at least \(r(x,y)-\sum_{i=1}^p\lfloor d_i/2\rfloor\). ``The proofs of [this theorem] and its applications are algorithmic and give rise to polynomial algorithms for constructing an \(r\)-edge connected \(f(s)\)-detachment, if it exists, and augmenting the local edge-connectivity of a graph or 3-hypergraph optimally.

Recommendations

Cited in

(17)

This page was built for publication: Detachments Preserving Local Edge-Connectivity of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4443122)