Journal of Combinatorics

Volume 7 (2016)

Number 2–3

Guest editors: Rong Luo and Cun-Quan Zhang

The Erdős–Sós conjecture for spiders of four legs

Pages: 271 – 283

DOI: https://dx.doi.org/10.4310/JOC.2016.v7.n2.a4

Authors

Genghua Fan (Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian, China)

Zhenxiang Huo (Institute of Disaster Prevention, Sanhe, Hebei, China)

Abstract

The Erdős–Sós Conjecture states that if $G$ is a graph with average degree more than $k-1$, then $G$ contains every tree of $k$ edges. A special case of the conjecture is the well-known Erdős–Gallai theorem: if $G$ is a graph with average degree more than $k-1$, then $G$ contains a path of $k$ edges. A spider is a tree with at most one vertex of degree more than $2$, called the center of the spider (if no vertex of degree more than two, then any vertex can be the center). A leg of a spider is a path from the center to a vertex of degree $1$. Thus, a path can be regarded as a spider of 1 or 2 legs. In this paper, we prove that if $G$ is a graph with average degree more than $k-1$, then $G$ contains every spider of 4 legs.

Keywords

Erdős–Sós Conjecture, trees, spiders

Published 23 February 2016