Embedding trees with maximum and minimum degree conditions

Main Article Content

Guido Besomi Matías Pavez-Signé Maya Stein

Abstract

We propose the following conjecture: For every fixed $\alpha\in [0,\frac 12]$, each graph of minimum degree at least $(1+\alpha)\frac k2$ and maximum degree at least $2(1-\alpha)k$ contains each tree with $k$ edges as a subgraph. \\ Our main result is an approximate version of the conjecture for bounded degree trees and large dense host graphs. We also show that our conjecture is asymptotically best possible, which disproves a conjecture from~\cite{rohzon}.

Article Details

How to Cite
Besomi, G., Pavez-Signé, M., & Stein, M. (2019). Embedding trees with maximum and minimum degree conditions. Acta Mathematica Universitatis Comenianae, 88(3), 457-462. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1316/680
Section
EUROCOMB 2019