Maximum induced trees in graphs

Let t(G) be the maximum size of a subset of vertices of a graph G that induces a 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, ρ{variant}), defined to be the minimum of t(G) over all connected graphs with n vertices and n - 1′ + ρ{variant} 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, ρ{variant}) is surprisingly small; in particular f(n, cn) = 2 loglogn + O(logloglogn) for any constant c > 0, and f(n, n^{1 + γ}) = 2 log(1 + 1 γ) ± 4 for 0 < γ < 1 and n sufficiently large. Bounds on t(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 for t(G) from the independence number α(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 - 1 vertices.