SIAM Journal on Algebraic and Discrete Methods · 1984 · 252 citations · 8 references
ComputingComputer ScienceComputational GeometryComputer NetworksInterconnection NetworksCommunication NetworksGraph TheoryNetwork SwitchingNetwork TheoryNetwork TopologyConcentrationGraph ConnectivityGraph Theory In Networks
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.
8
The nonexistence of certain generalized polygons
Walter Feit, Graham Higman · Journal of Algebra · 1964 · 357 citations
Nicholas Pippenger · SIAM Journal on Computing · 1977 · 119 citations
On non-linear lower bounds in computational complexity
Leslie G. Valiant · 1975 · 68 citations · Full text