Back to Search Start Over

A variant of the Erdős‐Sós conjecture

Authors :
Maya Stein
David R. Wood
Bruce Reed
Frédéric Havet
Combinatorics, Optimization and Algorithms for Telecommunications (COATI)
COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED)
Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S)
Université Nice Sophia Antipolis (... - 2019) (UNS)
COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S)
COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM)
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Center for Mathematical Modelling - Centro de Modelamiento Matematico [Santiago] (CMM)
Universidad de Chile = University of Chile [Santiago] (UCHILE)-Centre National de la Recherche Scientifique (CNRS)
Monash University [Melbourne]
Inria Sophia Antipolis - Méditerranée (CRISAM)
Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED)
Université Nice Sophia Antipolis (1965 - 2019) (UNS)
COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)
COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)
Source :
Journal of Graph Theory, Journal of Graph Theory, Wiley, 2020, 94 (1), pp.131-158. ⟨10.1002/jgt.22511⟩, Journal of Graph Theory, 2020, 94 (1), pp.131-158. ⟨10.1002/jgt.22511⟩
Publication Year :
2020
Publisher :
HAL CCSD, 2020.

Abstract

International audience; A well-known conjecture of Erdős and Sós 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 $[\frac{2m}{3}]$ contains every tree with m edges. As evidence for our conjecture we show (i) 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 (ii) there is a $\gamma > 0$ such that the weakening of the conjecture obtained by replacing $[\frac{2m} {3}$ by $(1 − \gamma)m$ holds.

Details

Language :
English
ISSN :
03649024 and 10970118
Database :
OpenAIRE
Journal :
Journal of Graph Theory, Journal of Graph Theory, Wiley, 2020, 94 (1), pp.131-158. ⟨10.1002/jgt.22511⟩, Journal of Graph Theory, 2020, 94 (1), pp.131-158. ⟨10.1002/jgt.22511⟩
Accession number :
edsair.doi.dedup.....5a349b5e12919f1dad99df5d0783c061