Home » Subject » Graph Theory » Basic G.T. » Connectivity
Importance: Medium ✭✭
Author(s): Kriesell, Matthias
Subject: Graph Theory
» Basic Graph Theory
» » Connectivity
Keywords: Disjoint paths
edge-connectivity
spanning trees
Recomm. for undergrads: no
Posted by: Jon Noel
on: August 25th, 2013
Conjecture   Let $ G $ be a graph and let $ T\subseteq V(G) $ such that for any pair $ u,v\in T $ there are $ 2k $ edge-disjoint paths from $ u $ to $ v $ in $ G $. Then $ G $ contains $ k $ edge-disjoint trees, each of which contains $ T $.

This problem was featured as unsolved problem #22 in Bondy and Murty's book "Graph Theory" [BM].

See also a posting on the open problem forum of the Egerváry Research Group on Combinatorial Optimization.

Bibliography

[BM] J. A. Bondy and U. S. R. Murty. Graph theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, 2008.


* indicates original appearance(s) of problem.
add new comment

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options