Barba, Luis and Fabila-Monroy, Ruy and Lara, Dolores and Leaños, Jesús and Rodrıguez, Cynthiaet 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.


Source : oai:HAL:hal-00990608v1
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

Browsing statistics

This page has been seen 66 times.
This article's PDF has been downloaded 109 times.