Explicit Concentrators from Generalized <i>N</i>-Gons

R. Michael Tanner

SIAM Journal on Algebraic and Discrete Methods · 1984 · 252 citations · 8 references

Concepts

Abstract

Concentrators are graphs used in the construction of switching networks that exhibit high connectivity. A technique for establishing the concentration properties of a graph by analysis of its eigenvalues is given. If the ratio of the subdominant eigenvalue to the dominant eigenvalue is small, the graph is a good concentrator. Generalized N-gons are very sparse, locally tree-like graphs for which the eigenvalues can be calculated with relative ease. The eigenvalue ratios for the known N-gons are calculated and show that the N-gons are excellent concentrators.

References

8