Add to ORKGWe prove that, if $m$ is sufficiently large, every graph on $m+1$ vertices that has a universal vertex and minimum degree at least $\lfloor \frac{2m}{3} \rfloor$ contains each tree $T$ with $m$ edges as a subgraph. Our result confirms, for large $m$, an important special case of a conjecture by Havet, Reed, Stein, and Wood. The present paper builds on the results of a companion paper in which we proved the statement for all trees having a vertex that is adjacent to many leaves.Comment: 31 page
AbstractFor a connected simple graph G let L(G) denote the maximum number of leaves in any spanning ...
AbstractLoebl, Komlós, and Sós conjectured that if at least half of the vertices of a graph G have d...
The Bandwidth Theorem of Böttcher, et al. [Mathematische Annalen 343 (2009), 175–205] gives minimum ...
In 2001, Komlós, Sárközy and Szemerédi proved that, for each α>0, there is some c>0 and n0 such that...
AbstractFor every n, we describe an explicit construction of a graph on n vertices with at most O(n2...
AbstractLet T be a tree and m be a positive integer. The leaf degree of a vertex x∈V(G) is defined a...
A connected graph having large minimum vertex degree must have a spanning tree with many leaves. In ...
\newcommand{\subdG}[1][G]{#1^\star} Given a graph $G$ and a positive integer $k$, we study the que...
Suppose G is a simple graph with average vertex degree greater than k - 2. Erdös and Sós conjectured...
Given a family $\mathcal{H}$ of graphs, a graph $G$ is called $\mathcal{H}$-universal if $G$ contain...
A tree T_uni is m-universal for the class of trees if for every tree T of size m, T can be obtained ...
The Erdös–Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k − 1)/2 co...
We prove that there is $c>0$ such that for all sufficiently large $n$, if $T_1,\dots,T_n$ are any tr...
Let λ(G) denote the smallest number of vertices that can be removed from a non-empty graph G so tha...
AbstractThe purpose of this paper is to initiate study of the following problem: Let G be a graph, a...
AbstractFor a connected simple graph G let L(G) denote the maximum number of leaves in any spanning ...
AbstractLoebl, Komlós, and Sós conjectured that if at least half of the vertices of a graph G have d...
The Bandwidth Theorem of Böttcher, et al. [Mathematische Annalen 343 (2009), 175–205] gives minimum ...
In 2001, Komlós, Sárközy and Szemerédi proved that, for each α>0, there is some c>0 and n0 such that...
AbstractFor every n, we describe an explicit construction of a graph on n vertices with at most O(n2...
AbstractLet T be a tree and m be a positive integer. The leaf degree of a vertex x∈V(G) is defined a...
A connected graph having large minimum vertex degree must have a spanning tree with many leaves. In ...
\newcommand{\subdG}[1][G]{#1^\star} Given a graph $G$ and a positive integer $k$, we study the que...
Suppose G is a simple graph with average vertex degree greater than k - 2. Erdös and Sós conjectured...
Given a family $\mathcal{H}$ of graphs, a graph $G$ is called $\mathcal{H}$-universal if $G$ contain...
A tree T_uni is m-universal for the class of trees if for every tree T of size m, T can be obtained ...
The Erdös–Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k − 1)/2 co...
We prove that there is $c>0$ such that for all sufficiently large $n$, if $T_1,\dots,T_n$ are any tr...
Let λ(G) denote the smallest number of vertices that can be removed from a non-empty graph G so tha...
AbstractThe purpose of this paper is to initiate study of the following problem: Let G be a graph, a...
AbstractFor a connected simple graph G let L(G) denote the maximum number of leaves in any spanning ...
AbstractLoebl, Komlós, and Sós conjectured that if at least half of the vertices of a graph G have d...
The Bandwidth Theorem of Böttcher, et al. [Mathematische Annalen 343 (2009), 175–205] gives minimum ...