The Erdös-Sós conjecture for spiders |
| |
Authors: | Genghua Fan |
| |
Institution: | a Department of Mathematics, Fuzhou University, Fujian 350002, PR China b Department of Maths and Informatics Sciences, College of Basic Sciences, Huazhong Agricultural University, Wuhan, 430070, PRChina |
| |
Abstract: | A classical result on extremal graph theory is the Erdös-Gallai theorem: if a graph on n vertices has more than 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 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. |
| |
Keywords: | Erdö s-Só s conjecture Trees Spiders |
本文献已被 ScienceDirect 等数据库收录! |
|