Barba, Luis and Fabila-Monroy, Ruy and Lara, Dolores and Leaños, Jesús and Rodrıguez, Cynthia et al. - The Erdős-Sós conjecture for geometric graphs

dmtcs:628 - Discrete Mathematics & Theoretical Computer Science, February 28, 2013, Vol. 15 no. 1
The Erdős-Sós conjecture for geometric graphs

Authors: Barba, Luis and Fabila-Monroy, Ruy and Lara, Dolores and Leaños, Jesús and Rodrıguez, Cynthia and Salazar, Gelasio and Zaragoza, Francisco

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.


Volume: Vol. 15 no. 1
Section: Combinatorics
Published on: February 28, 2013
Submitted on: July 5, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 164 times.
This article's PDF has been downloaded 457 times.