The Erdös-Sós Conjecture for Short-leg Spiders
Date Issued
2006
Date
2006
Author(s)
Lee, Chun-Ting
DOI
en-US
Abstract
A classical result on extremal graph theory is the Erd˝os-Gallai Theorem: if a graph with n vertices has more than (k−1)n/2 edges, then it contains a path of k edges. Motivated by the result, Erd˝os and S´os conjectured that under the same condition, the graph should contain
every tree of k edges. A spider is a tree in which each vertex has degree 1 or 2, except for possibly one vertex, called the center of the spider. A leg of a spider is a path from the center to a vertex of degree one.
Thus, a path is a spider of 1 or 2 legs. In this thesis, we prove that if a graph with n vertices has more than (k−1)n/2 edges, then it contains every k-edge spider whose legs are of length at most 4 except exactly one is of length 5. In addition, we also prove that a Hamiltonian graph with n vertices and more than (k−1)n/2 edges contains every spider of k edges.
Subjects
蜘蛛圖
Erdö
s-Só
s猜想
spiders
s conjecture
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-R93221028-1.pdf
Size
23.53 KB
Format
Adobe PDF
Checksum
(MD5):94ec2478483bb72bb1fc5fabdc7ef0f1