# High connectivity keeping spanning trees

(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) ≤ ck^{2} 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.

# References

[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?