The Erdős-Sós Conjecture for Geometric Graphs
Ruy Fabila-Monroy, Luis Felipe Barba, Dolores Lara, Jesús Leaños, Cynthia Rodríguez, Gelasio Salazar, Francisco Zaragoza
Abstract
Let f(n,k) be the minimum number of edges that must be
removed from some complete geometric graph G on
n points, so that there exists a tree on k
vertices that is no longer a planar subgraph of G. In
this paper we show that ( 1 / 2
)n2 / k-1-n / 2≤f(n,k) ≤2
n(n-2) / k-2. For the case when k=n,
we show that 2 ≤f(n,n) ≤3. For the case when
k=n and G is a geometric graph on a set of
points in convex position, we completely solve the problem and prove
that at least three edges must be removed.
Full Text: PDF PostScript