Maximum induced trees in graphs
type: Item
instance of: scholarly article
title: Maximum induced trees in graphs
zbMATH Open document ID: 0603.05023
DOI: 10.1016/0095-8956(86)90028-6
author: Vera T. Sós
author: Michael Saks
author: P. Erdős
published in: Journal of Combinatorial Theory. Series B
publication date: 1986-01-01T00:00:00Z
full work available at URL: 1-s2.0-0095895686900286-main.pdf
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 3972887
zbMATH Keywords: induced tree
zbMATH Keywords: NP completeness
zbMATH Keywords: radius
zbMATH Keywords: independence number
MaRDI profile type: Publication
OpenAlex ID: W2136253510
Wikidata QID: Q56388813
cites work: Q3852212
cites work: Graph Theory and Probability. II
cites work: Q5759552
cites work: Q4198056
cites work: Q3903002
cites work: Q5781249
description: scientific article; zbMATH DE number 3972887