The LMS-EPSRC Durham Research Symposia began in 1974, and form an established series of international research meetings, with nearly 100 symposia to date. They provide an excellent opportunity to explore an area of research in depth, to learn of new developments, and to instigate links between different branches. The format is designed to allow substantial time for interaction and research. The meetings are held in July and August, usually lasting for 10 days, with up to 70 participants, roughly half of whom will come from the UK. Lectures and seminars take place in the Department of Mathematical Sciences, Durham University.

**Outline**

Graph theory is a highly active mathematical discipline playing a central role in a variety of research fields with numerous applications far beyond mathematics. In this conference we aim to bring together researchers in pure mathematics and theoretical computer science whose scientific interests range from algorithmic and combinatorial topics to geometric, group theoretic and spectral aspects in graph theory.

The three topics will be central to the symposium. They are not independent but have many cross-links.

**Algorithmic Graph Theory and Complexity.**
Many computational problems in graph theory arise from practical questions.
These include network flow problems (max-flow min-cut), vertex- and
edge-connectivity (network reliability), matchings (assignment
problems), Eulerian tours and Chinese Postman Problem, Hamiltonian
cycles and Travelling Salesman Problem, vertex- and edge-colouring
(scheduling, time-tabling), stable sets, dominating sets.

**Combinatorial Graph Theory.**
One of the many tools in combinatorial graph
theory is the Tutte polynomial, counting many important properties such
as colourings, acyclic or totally cyclic orientations, spanning trees
and forests, and more. This topic links also up with computational
complexity from the previous section. Another thriving area is extremal
graph theory. There are also many links with other areas such as coding
theory and design theory. Statistical optimality of designs is closely
related to graph properties determined by the Laplacian spectrum,
mentioned in the next section.

**Graphs, Geometry and Spectra.**
There are close links betweem graph theory and differential geometry.
A differentiable manifold can be discretized by a weighted graph, and
the graph Laplacian approximates the Laplacian of the manifold. Results
from differential geometry have been applied to graphs. In addition,
one of the most celebrated applications of graph spectra is to Google's
page-rank algorithm. In optimal design theory in statistics, good designs
are found by maximizing functions of the Laplacian eigenvalues of the
concurrence graph. Expander graphs are of great theoretical and practical
importance, with applications in combinatorial number theory, finite
group theory, complexity theory and elsewhere.

**Travel Information**

Useful information about travelling to Durham can be found on the Department of Mathematical Sciences and Durham University webpages.

**Accommodation**

Accommodation for participants will be in a Durham College. Guest rooms offer en-suite and internet facilities. Attendance is by invitation only and fees for self-supporting participants are payable by cash, credit card, sterling cheques or sterling travellers cheques at registration.

**Organising Committee:**

Peter Cameron (QMUL), Norbert Peyerimhoff (Durham), Alina Vdovina (Newcastle).

**Scientific Adviser:**

Hajo Broersma (Twente).