Indexed by:
Abstract:
A classical result on extremal graph theory is the Erdos-Gallai theorem: if a graph on n vertices has more than (k-1)n/2 edges, then it contains a path of k edges. Motivated by the result, Erdos and Sos 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 (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 Wozniak on spiders of diameter at most 4. (C) 2007 Elsevier B.V. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
DISCRETE MATHEMATICS
ISSN: 0012-365X
Year: 2007
Issue: 23
Volume: 307
Page: 3055-3062
0 . 3 7 7
JCR@2007
0 . 7 0 0
JCR@2023
ESI Discipline: MATHEMATICS;
JCR Journal Grade:3
Cited Count:
WoS CC Cited Count: 15
SCOPUS Cited Count: 23
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 4
Affiliated Colleges: