Using the spectral graph theory techniques to search for strongly regular and distance regular graphs (D. Stevanović)

The technique of star complements was employed successfully to several problems in recent years, for example, to complete the characterization of graphs with least eigenvalue -2. In short, a star complement for an eigenvalue λ of multiplicity m in an n-vertex graph G is any (n-m)-vertex induced subgraph H of G which does not have λ as an eigenvalue. The Reconstruction theorem says that, in principle (and most of the time, in practice as well), a graph can be reconstructed if we know an eigenvalue and a corresponding star complement only.

Here we want to discuss to what extent star complements may be used to determine strongly regular or distance regular graphs with a given set of parameters. While there were a few applications of star complements to strongly regular graphs already, they were restricted to characterizing maximal graphs having some small graph as a star complement (e.g., the McLaughlin graph has 6K₁ ∪ K_1,16 as a star complement for eigenvalue 2).

So far I have shown, together with my PhD student, that they can be applied successfully to recently characterized SRGs with parameters (81,20,1,6) or (105,32,4,12), which both have 2 as the second eigenvalue. It appears that star complement technique might be applicable to other graphs with small second eigenvalue of large multiplicity, but the true potential of its applicability to SRGs or DRGs is still rather questionable. Evenmore, there are fundamental questions that need to be resolved as well: for example, it is not yet known whether every induced subgraph which does not have λ as an eigenvalue can be extended to a star complement?