Luis Barba ; Ruy Fabila-Monroy ; Dolores Lara ; Jesús Leaños ; Cynthia Rodrıguez 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 - https://doi.org/10.46298/dmtcs.628
The Erdős-Sós conjecture for geometric graphs

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

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 197 times.
This article's PDF has been downloaded 521 times.