No CrossRef data available.
Article contents
On the Expansion of the Giant Component in Percolated (n, d,λ) Graphs
Published online by Cambridge University Press: 01 May 2007
Abstract
Let d ≥ d0 be a sufficiently large constant. An graph G is a d-regular graph over n vertices whose second-largest (in absolute value) eigenvalue is at most . For any 0<p<1, Gp is the graph induced by retaining each edge of G with probability p. It is known that for the graph Gp almost surely contains a unique giant component (a connected component with linear number vertices). We show that for the giant component of Gp almost surely has an edge expansion of at least .
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2006