Expanding graphs contain all small trees
type: Item
instance of: scholarly article
title: Expanding graphs contain all small trees
zbMATH Open document ID: 0624.05028
DOI: 10.1007/BF02579202
author: Nicholas Pippenger
author: Joel Friedman
published in: Combinatorica
publication date: 1987-01-01T00:00:00Z
review text: Let N(S) denote the set of neighbors of the vertices in set S. Then the authors prove if G is a non-empty graph such that for every set S with at least 2n-2 vertices, \(| N(S)| \geq (d+1)| S|\), then G contains every tree with n vertices and maximum degree at most d. Moreover, for fixed d and any real number \(0<s<1\), then for every n there exists a graph G with O(n) edges such that every subgraph with fraction s of G's edges contains every tree with n vertices and maximum degree at most d.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4012640
zbMATH Keywords: tree
zbMATH Keywords: maximum degree
reviewed by: Alan C. Tucker
Wikidata QID: Q105583321
MaRDI profile type: Publication
cites work: Explicit construction of linear sized tolerant networks
cites work: On size Ramsey number of paths, trees, and circuits. I
cites work: Q3880849
cites work: Hamiltonian circuits in random graphs
full work available at URL: https://doi.org/10.1007/bf02579202
OpenAlex ID: W2086253307
description: scientific article; zbMATH DE number 4012640