Maximum induced trees in graphs (Q1082351)

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 \text{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.