کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420609 | 683961 | 2008 | 8 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Edge-splittings preserving local edge-connectivity of graphs Edge-splittings preserving local edge-connectivity of graphs](/preview/png/420609.png)
Let G=(V+s,E)G=(V+s,E) be a 2-edge-connected graph with a designated vertex s . A pair of edges rs,strs,st is called admissible if splitting off these edges (replacing rs and st by rt ) preserves the local edge-connectivity (the maximum number of pairwise edge disjoint paths) between each pair of vertices in VV. The operation splitting off is very useful in graph theory, it is especially powerful in the solution of edge-connectivity augmentation problems as it was shown by Frank [Augmenting graphs to meet edge-connectivity requirements, SIAM J. Discrete Math. 5(1) (1992) 22–53]. Mader [A reduction method for edge-connectivity in graphs, Ann. Discrete Math. 3 (1978) 145–164] proved that if d(s)≠3d(s)≠3 then there exists an admissible pair incident to s . We generalize this result by showing that if d(s)⩾4d(s)⩾4 then there exists an edge incident to s that belongs to at least ⌊d(s)/3⌋⌊d(s)/3⌋ admissible pairs. An infinite family of graphs shows that this bound is best possible. We also refine a result of Frank [On a theorem of Mader, Discrete Math. 101 (1992) 49–57] by describing the structure of the graph if an edge incident to s belongs to no admissible pairs. This provides a new proof for Mader's theorem.
Journal: Discrete Applied Mathematics - Volume 156, Issue 7, 1 April 2008, Pages 1011–1018