Timeline for Spanning trees of $H \cup e$ in terms of $H$
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 13, 2011 at 14:36 | comment | added | Brendan McKay | If $H$ has edge connectivity $c$, then each spanning forest of $H$ with exactly two components, one containing $u$ and the other containing $v$, can be made into a spanning tree of $H$ by adding at least $c$ different edges. In the other direction, as before a spanning tree of $H$ can be made into a 2-forest thing in at most $n-1$ ways. So $\kappa'(H) \le (n-1)\kappa(H)/c$, which I think implies that $\kappa(H+e) \le (n+c-1)\kappa(H)/c$. | |
| Sep 13, 2011 at 13:48 | comment | added | David Harris | And adding $s$ edges yields $\kappa(H + e_1 + \dots e_s) \leq \binom{s+n-1}{n-1} \kappa(H)$ by a similar argument. Can one improve this bound by taking advantage of the fact that when $\kappa(H)$ is big the spanning trees obtained from different spanning trees of $\kappa(H)$ necessarily overlap? | |
| Sep 13, 2011 at 9:05 | history | answered | Tony Huynh | CC BY-SA 3.0 |