### A variant of the Erdos-Sos conjecture

### Abstract

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.

### Más información

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 |

Volumen: | 94 |

Número: | 1 |

Editorial: | Wiley |

Fecha de publicación: | 2020 |

Página de inicio: | 131 |

Página final: | 158 |

Idioma: | English |

DOI: |
10.1002/JGT.22511 |

Notas: | ISI, SCOPUS |