zbMATH — the first resource for mathematics

Better expanders and superconcentrators. (English) Zbl 0641.68102
An explicit construction for expanders and superconcentrators is presented, using double covers of graphs. Eigenvalue arguments are used to establish the expansion properties. In this way, a family of n- superconcentrators with appoximately 123n edges is produced, improving on the best previous bound of 175n. The result in this paper has since been improved upon by using Ramanujan graphs; see A. Lubotzky, R. Phillips and P. Sarnak, “Explicit expanders and the Ramanujan conjectures”, Proc. 18th Symp. Theory Comput., 1986, 240-245.
Reviewer: C.J.Colbourn

68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI