June | 2011 | My Brain is Open

Today’s short post is about Kriesell’s conjecture. In my first year of PhD I enjoyed reading several papers related to this cute conjecture.

Nash-Williams [N’61] and Tutte [Tutte’61] independently proved that a graph $G(V,E)$ has $k$ edge-disjoint spanning trees if and only if $E(P) \geq k(|P|-1)$ for every partition $P$ of $V$ into non-empty classes, where $E(P)$ denotes the number of edges connecting distinct classes of $P$ . One interesting corollary of this result is the following :

Theorem : Every $2k$ -edge-connected graph has $k$ edge-disjoint spanning trees.

Let $G(V,E)$ be an undirected multigraph and $S \subseteq V$ . An $S-tree$ is a tree of $G$ that contains every vertex in $S$ . An $S-cut$ is a subset of edges whose removal disconnects some vertices in $S$ . A graph is $k-S-connected$ if every $S-cut$ has at least $k$ edges. Kriesell conjectured the following generalization of the above theorem.

Kriesell’s conjecture : If $G$ is $2k-S-connected$ , then $G$ has $k$ edge-disjoint $S-trees$ .

The first breakthrough towards proving Kriesell’s conjecture was by Lau. He proved that if G is $24k$ -edge-connected in $T$ then it has $k$ edge-disjoint Steiner trees. Recently, West and Wu [pdf] proved that it suﬃces for $S$ to be $6.5k$ -edge-connected in $G$ .

Open Problems

Obvious open problem is to prove or disprove Kriesell’s conjecture.

There a several related open problems about S-connectors in West-Wu’s paper.

References :

[Tutte’61] W.T.Tutte : On the problem of decomposing a graph into n connected factors, J. London Math. Soc. 36 (1961), 221–230.
[N’61] C.St.J.A.Nash-Williams : Edge disjoint spanning trees of ﬁnite graphs, J. London Math. Soc. 36 (1961), 445–450.
[Lau’07] L. C. Lau : An approximate max-Steiner-tree-packing min-Steiner-cut theorem. Combinatorica 27 (2007), 71–90