Month: June 2011

by

Kriesell’s Conjecture

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 suffices for S to be 6.5k-edge-connected in G.

Open Problems

  1. Obvious open problem is to prove or disprove Kriesell’s conjecture.
  2. 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 finite 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