Expanding Graphs Contain All Small Trees

Authors

Joel Friedman, University of California - Berkeley
Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1987

Abstract

The assertion of the title is formulated and proved. The result is then used to construct graphs with a linear number of edges that, even after the deletion of almost all of their edges or almost all of their vertices, continue to contain all small trees.

Rights Information

© 1987 Springer-Verlag

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1007/BF02579202

Recommended Citation

Friedman, J. and Pippenger, N. "Expanding Graphs Contain All Small Trees", Combinatorica, 7 (1987), 71-76. doi: 10.1007/BF02579202