An extension of a result concerning convex geometric graphs

2007/09/24 by Jesse Gilbert, Gilbert, Jesse
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM

paper · pdf · doi:10.48550/arxiv.0709.3590

This paper has been withdrawn by the author. This paper was presented at Discrete Math Days in Fort Collins Colorado

arxiv created 2010/07/29 · arxiv updated 2010/08/02

Abstract

We show a general result known as the Erdos_Sos Conjecture: if E(G)>1/2(k-1)n where G has order n then G contains every tree of order k+1 as a subgraph.

Related

• A local approach to the Erdős-Sós conjecture
• Embedding Nearly Spanning Trees
• On the Erdos-Sos Conjecture for Graphs on n=k+4 Vertices
• The Erdős-Sós Conjecture for Geometric Graphs
• A Variation of the Erdős-Sós Conjecture in Bipartite Graphs