Name
Abstract | ||
|---|---|---|
tree. We investigate the relationship of t(G)to other parameters associated with G : the number of vertices and edges, the radius, the independence number, maximum clique size and connectivity . The central result is a set of upper and lower bounds for the function f(n, p), defined to be the minimum of t(G)over all connected graphs with n vertices andn-1 +p edges. The bounds obtained yield an asymptotic characterization of the function correct to leading order in almost all ranges. The results show that f(n, p)is surprisingly small ; in particular ,fin, (n)=2loglogn+OfogloglogP) for any constant c>0, and fin,ti"T ) = 2log(I + 1 ~) ,)± 4 for 0<,,,< 1 and n sufficiently large . Bounds ont(G)are obtained in terms of the size of the largest clique . These are used to formulate bounds for a Ramsey-type function, N(k, t), the smallest integer so that every connected graph on N(k, t) vertices has either a clique of size k or an induced tree of size t.Tight bounds fort(G)from the independence number a(G)are also proved . It is shown that every connected graph with radius r has an induced path, and hence an induced tree, on 2r- I vertices . |
Year | DOI | Venue |
|---|---|---|
1986 | 10.1016/0095-8956(86)90028-6 | J. Comb. Theory, Ser. B |
Keywords | Field | DocType |
maximum induced tree,upper and lower bounds,connected graph | Discrete mathematics,Combinatorics,Tree (graph theory),Vertex (geometry),Clique,Upper and lower bounds,Induced path,Vertex (graph theory),Connectivity,Mathematics,Path graph | Journal |
Volume | Issue | ISSN |
41 | 1 | Journal of Combinatorial Theory, Series B |
Citations | PageRank | References |
45 | 6.93 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul Erdös | 1 | 111 | 23.10 |
| Michael Saks | 2 | 2595 | 302.11 |
| Vera T. Sós | 3 | 318 | 62.21 |