Non-existence of one-dimensional expanding graphs
- 1 October 1981
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 109-114
- https://doi.org/10.1109/sfcs.1981.23
Abstract
Expanding graphs are the basic building blocks used in constructions of graphs with special connectivity properties such as superconcentrators. The only known explicit method (Margulis[7], Gabber and Galil[5]) of constructing arbitrarily large expanding graphs with a linear number of edges, uses graphs whose edges are defined by a finite set of linear mappings restricted to a two-dimensional set, Zn × Zn, where Zn denotes the integers mod n. In this paper we prove that for any finite set of onedimensional linear mappings with rational coefficients, the graph they define by their restriction to Zn is not an expanding graph. We also show that shuffle exchange graphs can not be expanding graphs.Keywords
This publication has 12 references indexed in Scilit:
- On alternation IIActa Informatica, 1980
- Time-space tradeoffs for computing functions, using connectivity properties of their circuitsJournal of Computer and System Sciences, 1980
- Time-space tradeoffs for some algebraic problemsPublished by Association for Computing Machinery (ACM) ,1980
- On Concentrators, Superconcentrators, Generalizers, and Nonblocking NetworksBell System Technical Journal, 1979
- Explicit constructions of linear size superconcentratorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Generalized ConnectorsSIAM Journal on Computing, 1978
- SuperconcentratorsSIAM Journal on Computing, 1977
- Space bounds for a game on graphsTheory of Computing Systems, 1976
- Graph-theoretic properties in computational complexityJournal of Computer and System Sciences, 1976
- On non‐blocking switching networksNetworks, 1971