Maximum induced trees in graphs

Paul Erdös, Michael Saks, Vera T. Sós

Research output: Contribution to journalArticlepeer-review

86 Scopus citations

Abstract

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, n1 + γ) = 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.

Original languageEnglish (US)
Pages (from-to)61-79
Number of pages19
JournalJournal of Combinatorial Theory, Series B
Volume41
Issue number1
DOIs
StatePublished - Aug 1986

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Maximum induced trees in graphs'. Together they form a unique fingerprint.

Cite this