×

The Erdős-Sós conjecture for spiders. (English) Zbl 1126.05059

Summary: A classical result on extremal graph theory is the Erdős-Gallai theorem: if a graph on \(n\) vertices has more than \(\frac{(k-1) n}{2}\) edges, then it contains a path of \(k\) edges. Motivated by the result, Erdős and Sós conjectured that under the same condition, the graph should contain every tree of \(k\) edges. A spider is a rooted tree in which each vertex has degree one or two, except for the root. A leg of a spider is a path from the root to a vertex of degree one. Thus, a path is a spider of 1 or 2 legs. From the motivation, it is natural to consider spiders of 3 legs. In this paper, we prove that if a graph on \(n\) vertices has more than \(\frac{(k-1) n}{2}\) edges, then it contains every \(k\)-edge spider of 3 legs, and also, every \(k\)-edge spider with no leg of length more than 4, which strengthens a result of Woźniak on spiders of diameter at most 4; see M. Woźniak [J. Graph Theory 21, No. 2, 229–234 (1996; Zbl 0841.05017)].

MSC:

05C35 Extremal problems in graph theory
05C05 Trees

Citations:

Zbl 0841.05017
Full Text: DOI

References:

[1] Brandt, S.; Dobson, E., The Erdös-Sós conjecture for graphs of girth 5, Discrete. Math., 150, 411-414 (1996) · Zbl 0854.05064
[2] Erdös, P., Extremal problems in graph theory, (Fiedler, M., Theory of Graphs and its Applications (1965), Academic Press), 29-36 · Zbl 0161.20501
[3] Erdös, P.; Gallai, T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar., 10, 337-356 (1959) · Zbl 0090.39401
[4] F Saclé, J.; Woźniak, M., The Erdös-Sós conjecture for graphs without \(C_4\), J. Combin. Theory B, 70, 367-372 (1997) · Zbl 0878.05024
[5] Sidorenko, A. F., Asymptotic solution for a new class of forbidden \(r\)-graphs, Combinatorica, 9, 207-215 (1989) · Zbl 0732.05031
[6] Woźniak, M., On the Erdös-Sós conjecture, J. Graph Theory, 21, 229-234 (1996) · Zbl 0841.05017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.