Geodesic
Approximating the isoperimetric number of strongly regular graphs
The electronic journal of linear algebra, Tome 13 (2005), pp. 111-121.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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.
Classification : 05C50, 15A42, 52B12
Keywords: strongly regular graphs, Laplacian, linear programming 
@article{ELA_2005__13__a18,
     author = {Sivasubramanian, Sivaramakrishnan},
     title = {Approximating the isoperimetric number of strongly regular graphs},
     journal = {The electronic journal of linear algebra},
     pages = {111--121},
     publisher = {mathdoc},
     volume = {13},
     year = {2005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ELA_2005__13__a18/}
}
TY  - JOUR
AU  - Sivasubramanian, Sivaramakrishnan
TI  - Approximating the isoperimetric number of strongly regular graphs
JO  - The electronic journal of linear algebra
PY  - 2005
SP  - 111
EP  - 121
VL  - 13
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ELA_2005__13__a18/
LA  - en
ID  - ELA_2005__13__a18
ER  - 
%0 Journal Article
%A Sivasubramanian, Sivaramakrishnan
%T Approximating the isoperimetric number of strongly regular graphs
%J The electronic journal of linear algebra
%D 2005
%P 111-121
%V 13
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ELA_2005__13__a18/
%G en
%F ELA_2005__13__a18
Sivasubramanian, Sivaramakrishnan. Approximating the isoperimetric number of strongly regular graphs. The electronic journal of linear algebra, Tome 13 (2005), pp. 111-121. http://geodesic.mathdoc.fr/item/ELA_2005__13__a18/