The ErdosSós conjecture for geometric graphs
Article

 Overview

 Research

 Additional Document Info

 View All

Overview
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/k1  n/2 ≤ f(n, k) ≤ 2 n(n2)/k2. 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. © 2013 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.
publication date
published in
Research
keywords

Extremal graph theory; Geometric graph; Spanning tree Extremal graph theory; Geometric graphs; Spanning tree; Subgraphs; Geometry; Graph theory
Additional Document Info
start page
end page
volume
issue