The Department Home Prospective Students Staff List Research Information Conferences and Workshops Industrial Liaison Departmental Vacancies Alumni Contact Us Other Links

Computing Science Current Student Information Computing Science Seminars

Maths and Stats Group M&SG Home Page Mathematics Seminars Statistical Service

The University University Home Page Student/Staff Portal WebCT

Algebraic Graph Theory

Staff

• Peter Rowlinson

Research Students

• Penny Jackson, PhD, 1999

Current and Recent Visitors

• Prof Dragos Cvetkovic (Belgrade), 2001

Current and Recent Projects

• Workshop on Algebraic Graph Theory, International Centre for Mathematical Sciences (Edinburgh), 2001.
• An algebraic investigation of network papers with prescribed substructures, EPSRC, 1998.
• Lectures in Sicily (2002), Serbia & Montenegro (2003).
• The research monograph `Spectral Generalizations of Line Graphs', by D. Cvetkovic, P. Rowlinson and S. Simic was published by Cambridge University Press in July 2004 (ISBN 0521-83663-8).
• D. Cvetkovic and P. Rowlinson contributed the chapter on Spectral Graph Theory for `Topics in Algebraic Graph Theory' (eds L. W. Beineke and R. J. Wilson), published by Cambridge University Press in November 2004 (ISBN 0521-80197-4).

Research Activities

• 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.