The Erdos-Só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/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. © 2013 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.

authors

• Barba L.
• Fabila-Monroy R.
• Lara D.
• Leaños J.
• Rodríguez C.
• Salazar Anaya Gelasio
• Zaragoza F.J.

publication date

• 2013-01-01

published in

• Discrete Mathematics and Theoretical Computer Science  Journal

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

• 93

end page

• 100

volume

• 15

issue

• 1