ELA, Volume 13, pp. 111-121, April 2005, abstract.
Approximating the Isoperimetric Number of
Strongly Regular Graphs
Sivaramakrishnan Sivasubramanian
A factor 2 and a factor 3 approximation algorithm
are given for the isoperimetric number of Strongly
Regular Graphs. One approach involves eigenvalues
of the combinatorial laplacian of such graphs.
In this approach, both the upper and lower bounds
involve the spectrum of the combinatorial laplacian.
An interesting inequality is proven between the second
smallest and the largest eigenvalue of combinatorial
laplacian of strongly regular graphs. This yields a
factor 3 approximation of the isoperimetric number.
The second approach, firstly, finds properties of
the metric which is returned by the linear programming
formulation of [Linial et. al., The geometry of graphs
and some of its algorithmic applications, Combinatorica,
vol. 15(2) (1995), pp. 215-245] and secondly, gives an
explicit cut which is within factor 2 of the optimal
value of the linear program. The spectral algorithm
can be generalized to get a factor 3 approximation for
a variant of the isoperimetric number for Strongly
Regular Graphs.