## EuroWorkshop on Algebraic Graph Theory

### Edinburgh 9-13 July 2001

Workshop Arrangements | Scientific Programme | Participants List | Call for Papers | Application Forms | Workshop Home Page

### Scientific Programme

Timetable
Talks by key speakers are linked to abstracts - click on the highlighted names to see the abstract. Abstracts for all talks will be published in the Conference Pack.

Use these links to go to a particular day in the timetable.

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

 Monday 9 July 0915-0930 Welcome/introduction 0930-1030 W. HaemersWhich graphs are determined by their spectra? 1100-1130 E. van Dam Edge-decompositions of the complete graph into strongly regular graphs 1140-1210 P. van den Driessche Maximal graphs and graphs with maximal spectral radiusM. NoyRecursive constructions of graphs and Tutte polynomials 1430-1450 E. KuijkenSome non-existence results for regular graphs in regular two-graphsJ. Katriel Permutations as powers of cycles of equal length and enumeration of hypertrees 1500-1520 M. MitjanaWeakly distance-regular digraphsP. ChebotarevOut forests of a digraph, the Kirchhoff matrix,and Markov chain probabilities 1530-1550 M. KlinA computational approach to partial difference sets 1620-1720 B. ShaderSpectra of Tournaments

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

 Tuesday 10 July 0930-1030 P. W. FowlerEigenvalues at work in chemistry: fullerenes as graphs and molecules 1100-1130 R. KingAutomorphism groups and spectra of highly symmetrical graphs 1140-1210 K. TaylorSpectra of block Toeplitz matricesD. Olesky Digraphs with large exponent 1430-1450 D. StevanovicConstructing fullerene graphs from their eigenvalues and anglesM. Lang Bipartite distance-regular graphs and representation diagrams 1500-1520 D. MojdehGraphs, codes and their applications 1530-1550 I. KovacsSome applications of the discrete Fourier transformation in graph theory 1620-1720 P. HansenComputers and discovery in graph theory

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

 Wednesday 11 July 0930-1030 N. L. Biggs Algebraic methods for chromatic polynomials. 1100-1130 H. BielakThe zeros of chromatic polynomials of graphs M. MuzychukIsomorphism problem for circulants 1140-1210 C. Cerf Graphs of knots and linksP. Cara Incidence geometry and graphs

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

 Thursday 12 July 0930-1030 D. CvetkovicGraphs with least eigenvalue -2 1100-1150 P. RowlinsonA survey of star complements 1200-1220 I. Sciriha Polynomial reconstruction for a class of disconnected graphsW. KorczynskiOn a presentation of graphs 1430-1450 M. Lepovic Some results on graphs with exactly two main eigenvaluesR. WhittyDiagonalising the Laplacian of a directed tree 1500-1520 D. BokalEmbedding cartesian products of graphs by using eigenvectors of Laplacian matrixK. MarkstromIsomagnetic Graphs 1530-1550 N. Abreu & C. OlivieraThe characteristic polynomial of the Laplacian of (a,b)-linear class of graphsL. HellstromHow many steps does the Gauss-Jordan elimination require? 1620-1720 B. MoharMinor monotone spectral invariants of graphs

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

 Friday 13 July 0930-1030 M. A. FiolSpectral bounds and distance-regularity 1100-1130 P. Terwilliger Recent progress on the subconstituent algebra of a distance-regular graph 1140-1210 J. Caughman Classical parameters and bipartite distance-regular graphs 1430-1500 L. JorgensenDirected strongly regular graphs, construction and non-existence 1530-1630 P. J. CameronStrongly regular graphs: from scarcity to plenty

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

Abstracts

N L BIGGS
Algebraic Methods for Chromatic Polynomials.
I shall discuss recent developments in the 'transfer matrix' method for calculating chromatic polynomials of families of graphs. The idea is to define invariant subspaces on which it is possible to calculate the action of the matrix. The resulting eigenvalues and multiplicities determine a formula for the chromatic polynomial, and the method links well with analytic methods for locating the zeros of the polynomial.

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

P J CAMERON
Strongly regular graphs: from scarcity to plenty
Graphs satisfying strong symmetry conditions tend to be rare. On the other hand, regular graphs are so plentiful that a well-developed theory of random regular graphs exists. Strongly regular graphs lie somewhere between these two extremes. For some parameter values, they are unique or fail to exist, while for other values they exist in great profusion and invite the discussion of random objects and their properties.

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

D CVETKOVIC
Graphs with least eigenvalue -2
Graphs with least eigenvalue -2 can be represented by sets of vectors at 60 or 90 degrees, via the corresponding Gram matrices. Maximal sets of lines through the origin with such mutual angles are closely related to the root systems known from the theory of Lie algebras. Using such a geometrical characterization one can show that graphs in question are either generalized line graphs (representable in the root system D_n for some n) or exceptional graphs (representable in the exceptional root system E_8).

We present several results on generalized line graphs and on exceptional graphs; some are new and some are old but from new view points. In particular, we describe how the maximal exceptional graphs, 473 in number, have recently been determined independently by a Serbian-British and a Japanese group of researchers using computers, and then constructed theoretically by the first group. The recent star complement technique approach to the study of graphs with least eigenvalue -2 can be used as an alternative to the root system technique, but the construction was achieved by combining both techniques. Other results include the assertion that a connected graph with least eigenvalue -2 is exceptional if and only if it has an exceptional star complement for the eigenvalue -2, and a description of the eigenspace for -2 in generalized line graphs.

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

M A FIOL
Spectral bounds and distance-regularity
We shall give a survey of recent results showing that the usual concepts of (local or global) distance-regularity in a graph can be thought of as an extremal (numeric) property of the graph. This is because such structures appear when a certain spectral bound is attained, so yielding striking characterizations of distance-regularity, with the peculiarity of involving only numerical (instead of the usual matricial) identities.

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

P W FOWLER
Eigenvalues at work in chemistry: fullerenes as graphs and molecules
Chemistry is both a fertile source for, and consumer of, mathematical conjectures in graph theory. Chemists use adjacency matrices and their eigenvalues to characterise stability and reactivity of unsaturated carbon frameworks. They are interested in regularities, even if not perfect, such as the famous Huckel 4n+2 rule, and the equivalents for 3-dimensional systems such as fullerenes. The power and limitations of such graph-theory based reasoning in the chemistry and physics of the fullerenes and nanotubes will be discussed, as will the use of distance matrices, independence numbers and codes in modelling the addition chemistry of fullerenes. Physically based analogies suggest a relation between distance and adjacency spectra of fullerenes and other cage molecules, and geometric constructions for specific `leapfrog' fullerenes suggest many chemically relevant conjectures.

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

W HAEMERS
Which graphs are determined by their spectra?
This question is old, but far from solved. It is conceivable that almost all graphs are determined by the spectrum (for short, DS), but it is also still possible that almost no graphs are DS.

For non-DS graphs, several constructions are known. Schwenk proved (in 1974) that allmost all trees are not DS, and Godsil and McKay showed that the proportion of non-DS graphs on n vertices is at least c(n^3)/(2^n) for some constant c.

Most graphs that are known to be DS are either small, so that the property can be proved by complete enumeration, or they have a high degree of regularity. The latter examples are mainly distance-regular graphs (including the complete graphs) and line graphs of smaller DS graphs.

The aim of the talk is to survey the known DS and non-DS graphs.

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

P HANSEN
Computers and discovery in graph theory
In the last two decades, several systems have been proposed to help the graph theorist in finding conjectures and refutations. They are based on quite different principles: interactive computation of graph invariants and sensitivity analysis (Cvetkovic's system GRAPH), algebraic characterization of graph properties and generation of new concepts (Epstein's system GRAPH THEORIST), algebraic manipulation of graphical formulas (Brigham and Dutton's system INGRID), generation of many simple conjectures and heuristic elimination of dull ones (Fajtlowicz's system GRAFFITI), determination and analysis of extremal or near-extremal graphs (Caporossi and Hansen's system AUTOGRAPHIX). Graph enumeration systems (such as e.g. McKay's system GENG) can play a similar role. These systems will be surveyed, with an emphasis on open problems and possible improvements through hybridation.

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts

B MOHAR
Minor monotone spectral invariants of graphs
Several graph invariants based on the spectra of matrices associated with the graph, with the property that they are minor monotone, will be presented and compared. The presentation will include the Colin de Verdiere parameter $\mu$, the related invariants $\nu$ and $\lambda$, the Lovasz function $\theta$, and invariants based on the second smallest Laplacian

Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts