Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 603.05023
Autor: Erdös, Paul; Saks, Michael; Sós, Vera T.
Title: Maximum induced trees in graphs. (In English)
Source: J. Comb. Theory, Ser. B 41, 61-79 (1986).
Review: The paper studies t(G) = maximum size of a subset of vertices of a graph that induces a tree. Upper and lower bounds are established in terms of other invariants of G. There is a lower bound in terms of the radius: t(G) \geq 2 rad(G)-1. With \alpha being the independence number and 1 \leq m \leq (n-1)/2 holds: \alpha (G) > ((m-1)n)/m+1 implies t(G) \geq 2m+1 and \alpha (G) > ((m-1)n+1)/m+1 implies t(G) \geq 2m+2, these bounds being best possible (m = |E(G)|, n = |V(G)|). Let f(n,\rho) = minimum of t(G) over all graphs G with n vertices and n+\rho-1 edges. Upper and lower bounds for f(n,\rho) are obtained resulting in an almost complete description of the asymptotic behavior of f(n,\rho). This shows that f(n,\rho) is of a surprisingly small order. Relations between t(G) and the maximum clique size are proved: For k \geq 3, t \geq 2 there is a minimum integer N(k,t) such that every connected graph with at least N(k,t) vertices has either a clique of size k or an induced tree of size t. For N(k,t) bounds are derived. Finally, the problem "For given G and t is t(G) > t?'' is NP complete.
Reviewer: W.Dörfler
Classif.: * 05C35 Extremal problems (graph theory)
05C05 Trees
Keywords: induced tree; NP completeness; radius; independence number
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag