Changes

Jump to: navigation, search

Kriesell's conjecture

37 bytes removed, 09:43, 31 October 2009
/* Remarks */
[http://www.google.com/books?hl=en&lr=&id=PuL2KC_KCj0C&oi=fnd&pg=PA145&dq=W.+Mader,+A+reduction+method+for+edge-connectivity+in+graphs,+Ann.+Discrete+Math.+3+(1978),+145-164.&ots=7vnYFfZ-gu&sig=KQuIB555SzYrEhIPVkVziWnXeKA#v=onepage&q=&f=false]</ref>that the conjecture holds if the degree of every node in ''V-T'' is even. Jain et al. [3] found the following bound for the general case: if ''G'' is ''k''-edge-connected in ''T'', then ''G'' contains <math>\lfloor \alpha_{\vert T\vert}k \rfloor</math> edge-disjoint Steiner trees for ''T'', where <math>\alpha_i</math> can be defined recursively by <math>\alpha_2=1</math>, <math>\alpha_i=\alpha_{i-1}-\frac{\alpha_{i-1}^2}{4}</math> (''i''>2).
Comment (Tamás Király, 02.01.2004)
In [8], Petingi and Rodriguez prove that if $G$ is $k$-edge-connected in $T$ and $\vert T\vert\geq 2$, then $G$ contains at least $\lfloor (\frac{2}{3})^{\vert V-T\vert}k/2 \rfloor$ edge-disjoint Steiner trees for $T$.
Egresuser
40
edits