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.