Name
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1002/jgt.22511 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
Erdos-Sos conjecture,graph theory | Journal | 94.0 |
Issue | ISSN | Citations |
1.0 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frédéric Havet | 1 | 433 | 55.15 |
| Bruce A. Reed | 2 | 1311 | 122.69 |
| maya stein | 3 | 81 | 15.65 |
| David R. Wood | 4 | 1073 | 96.22 |