Back to Search
Start Over
A variant of the Erdős‐Sós conjecture
- 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.
- Subjects :
- Conjecture
Degree (graph theory)
010102 general mathematics
Graph theory
0102 computer and information sciences
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
01 natural sciences
Graph
Combinatorics
010201 computation theory & mathematics
Discrete Mathematics and Combinatorics
Geometry and Topology
0101 mathematics
Mathematics
Subjects
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