Decomposing rooted (k,l)-connected graphs into rooted k-connected parts

From Egres Open
Jump to: navigation, search

Let G=(V,E) be an undirected graph, and [math]r \in V[/math] a root node. G is called rooted (k,l)-connected if G-X is [math](k-\vert X\vert)l[/math]-edge-connected for any [math]X \subseteq V-r[/math]. Is it true that every rooted (k,l)-connected graph contains l edge-disjoint spanning rooted k-connected subgraphs?


Remarks

A similar statement for connectivity between two nodes was shown to be true by Egawa, Kaneko, and Matsumoto [1]. Similar connectivity properties also have been studied in [2] and [3].

References

  1. ↑ Y. Egawa, A. Kaneko, M. Matsumoto, A mixed version of Menger's theorem, Combinatorica 11 (1991), 71-74. DOI link
  2. ↑ A. Kaneko, K. Ota, On minimally (n, λ)-connected graphs, J. Combin. Theory, Series B 80 (2000), 156-171. DOI link
  3. ↑ A.R. Berg, T. Jordán, Sparse certificates and removable cycles in l-mixed p-connected graphs, Oper. Res. Lett. 33 (2005), 111-114. DOI link EGRES Tech. Report
Retrieved from "http://lemon.cs.elte.hu/egres/internals/index.php5?title=Decomposing_rooted_(k,l)-connected_graphs_into_rooted_k-connected_parts&oldid=595"