A variant of the Erdos-Sos conjecture
A well-known conjecture of Erdos and Sos states that every graph with average degree exceeding m-1 contains every tree with m edges as a subgraph. We propose a variant of this conjecture, which states that every graph of maximum degree exceeding m and minimum degree at least [2m/3] contains every tree with m edges. As evidence for our conjecture we show (a) for every m there is a g(m) such that the weakening of the conjecture obtained by replacing the first m by g(m) holds, and (b) there is a gamma > 0 such that the weakening of the conjecture obtained by replacing [2m/3] by (1-gamma)m holds.
|Título según WOS:||A variant of the Erdos-Sos conjecture|
|Título según SCOPUS:||A variant of the Erd?s-Sós conjecture|
|Título de la Revista:||JOURNAL OF GRAPH THEORY|
|Fecha de publicación:||2020|
|Página de inicio:||131|