# Algebraic Graph Theory

- Construction and characterisation of graphs by means of star complements
- Spectral properties of graphs
- Graphs with least eigenvalue -2

The context for work in these areas is the relationship between the structure of a network graph and its algebraic invariants, which include the eigenvalues of an adjacency matrix. Associated with each such eigenvalue are corresponding subgraphs called star complements. Several graphs can be characterised as maximal graphs with a prescribed star complement for a prescribed eigenvalue. More generally, an algorithm is available for constructing all graphs with a given star complement. In joint work with colleagues from Serbia, this `star complement technique' was used in 1999 to solve a problem of some 25 years' standing, namely determination of the graphs with least eigenvalue -2 which are not generalised line graphs. In addition, new results by the Stirling mathematicians include sharp upper bounds for the multiplicities of graph eigenvalues, with an application to regular graphs.

Collaboration with researchers in the former Yugoslavia began in 1985 and is now well established, thanks in part to financial support from the Carnegie Foundation, EPSRC and the Serbian Academy of Sciences and Arts.

The Algebraic Graph Theory group at Stirling has organised the following international meetings:

- A workshop on Algebraic Graph Theory at the International Centre for Mathematical Sciences, Edinburgh in July 1993. This attracted 45 mathematicians from 17 countries. It was supported by SERC, the Edinburgh Mathematical Society, the London Mathematical Society, and the British Council.
- The 15th British Combinatorial Conference, held at Stirling in July 1995, and organised on behalf of the British Combinatorial Committee. This attracted 230 reseachers from 29 countries. It was supported by the London Mathematical Society ,and the Institute of Combinatorics and its Applications.
- A EuroWorkshop on Algebraic Graph Theory at the International Centre for Mathematical Sciences, Edinburgh in July 2001. This attracted 68 mathematicians, computer scientists and mathematical chemists from 21 countries. This was a High-Level Scientific Conference supported by the European Commission as part of its Framework V programme, with additional funding from the London Mathematical Society and the British Combinatorial Committee.

### Algebraic Graph Theory is part of: