High connectivity keeping spanning trees

From himtp
Revision as of 17:12, 27 September 2015 by Himuser (Talk | contribs) (Himuser moved page Matthias Kriesell's Problem to High connectivity keeping spanning trees)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

(suggested by Matthias Kriesell)

Problem Statement

It is an old question, attributed to L. Lovász [5], to decide whether for every k > 0 there exists a (smallest) f(k) such that in between any two vertices of an f(k)-connected graph G there exists an [induced] path P such that G - V(P) is k-connected. It is known that f(1) = 3 and f(2) = 5 (see [4]), whereas the existence of f(k) for any k > 2 is open. Some years ago I suggested to relax the question as follows: For every k > 0 there exists a (smallest) g(k) such that in between any two vertices of an g(k)-connected graph G there exists an [induced] path P such that G - E(P) is k-connected; this has been proven in [3], with g(k) ≤ ck2 for some constant c < 2000; it would follow from an affirmative answer to the following.

Conjecture: For every k > 0 there exists a (smallest) h(k) such that every h(k)-connected graph has a spanning tree T such that G - E(T) is k-connected.

What is known?

The analogue for edge-connectivity follows easily from Tutte's and Nash-Williams's base packing theorem (and yields h(1) = 4). By a result of T. Jordán on rigid bases [2], every 6k-connected graph has k edge-disjoint spanning 2-connected subgraphs, implying h(2) ≤ 12, which has been improved to h(2) ≤ 8 recently [1]. The existence of h(k) for any k > 2 is wide open.


[1] J. Cheriyan, O. Durand de Gevigney, and Z. Szigeti, Packing of rigid spanning subgraphs and spanning trees, J. Combin. Theory Ser. B 105 (2014), 17-25.

[2] T. Jordán, On the existence of k edge-disjoint 2-connected spanning subgraphs, J. Combin. Theory Ser. B. 95 (2005), 257-262.

[3] K. Kawarabayashi, O. Lee, B. Reed, and P. Wollan, A Weaker Version of Lovász Path Removal Conjecture, J. Combin. Theory Ser. B 98 (2008), 972-979.

[4] M. Kriesell, Induced paths in 5-connected graphs, J. Graph Theory 36 (2001), 52-58.

[5] C. Thomassen, Graph decompositions with applications to subdivisions and path systems modulo k, J. Graph Theory 7 (1983), 261-271.

Please add comments here

I recall hearing another problem on digraphs. Is there a function f(k) such that any f(k)-edge-connected digraph has k-edge-disjoint strongly-connected digraphs? It appears that one can prove a weak version where one says that if a digraph is (ck log n)-edge-connected (here c is some fixed constant) then there are k edge-disjoint strongly-connected digraphs. Is this interesting and/or known?