Premium
The Erdős‐Sós Conjecture for trees of diameter four
Author(s) -
McLennan Andrew
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20083
Subject(s) - mathematics , combinatorics , conjecture , vertex (graph theory) , graph , discrete mathematics
The Erdős‐Sós Conjecture is that a finite graph G with average degree greater than k − 2 contains every tree with k vertices. Theorem 1 is a special case: every k ‐vertex tree of diameter four can be embedded in G . A more technical result, Theorem 2, is obtained by extending the main ideas in the proof of Theorem 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 291–301, 2005