Non-separating n-trees up to diameter 4 in a (2n+2)-cohesive graph

摘要

A connected simple graph G is called κ ― cohesive if for any pair of distinct vertices u, ν ∈ V(G), d(u) + d(ν) + d(u,ν) ≥ κ. A subgraph H of a connected graph G is non-separating if G ― V(H) is connected. Locke conjectured that given a tree T on n vertices, n ≥ 3, any 2n ― cohesive graph has a non-separating copy of T. Here we prove that given a tree T on n vertices and diameter at most 4, any (2n + 2) ― cohesive graph has a non-separating copy of T.