Originator(s): Stephen C. Locke (communicated by Locke - REGS 2008)
Definitions: A subgraph of a connected graph G with vertex set S is non-separating if G-S is connected. A connected graph G is h-cohesive if d(u)+d(v)+d(u,v)≥h for all u,v∈V(G).
Conjecture 1: For k≥3, if G is a 2k-cohesive graph, then G contains a non-separating copy of every tree with k vertices.
Comments: Locke [L] posed the question for paths as Problem 10647 in the Monthly. The Monthly published a composite solution (for paths) "based on a solution by Phil Tracy with elements from a joint solution by S.C. Locke and H.-J. Voss and contributions by the editors." Abreu and Locke [AL] proved that if the diameter of a k-vertex tree T is at most 4, then every (2k+2)-cohesive graph contains a non-separating copy of T.
There are many ways to weaken the statement of the conjecture to pursue partial results. One can restrict the family of trees, such as to caterpillars, spiders (subdivisions of stars), etc., aiming to include the family of paths for which the conjecture is known to hold. One can increase the cohesiveness required, seeking the minimum cohesiveness for which the conclusion holds (the [AL] paper both specialized the trees and increased the cohesiveness). One can restrict the family of graphs for which the result is proved. For example, what is the smallest connectivity (or smallest minimum degree) of n-vertex graphs for which the conclusion can be proved?
In the other direction, one can consider particular trees and prove lower bounds on the cohesiveness that is required to force their appearance as non-separating subgraphs.
References:
[AL] Abreu, M.; Locke, S. C.;
Non-separating n-trees up to diameter 4 in a (2n+2)-cohesive
graph. Proceedings of the Thirty-third Southeastern International Conference on
Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002).
Congr. Numer. 154 (2002), 21--30.
[L] S. C. Locke, Problem 10647, MAA Monthly 105 (1998), 176.