EuroWorkshop on Algebraic Graph Theory
Edinburgh 9-13 July 2001
Scientific Programme
TimetableTalks 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.
Haemers Which 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 radius M. Noy Recursive constructions of graphs and Tutte polynomials |
| 1430-1450 | E. Kuijken Some non-existence results for regular graphs in regular two-graphs J. Katriel Permutations as powers of cycles of equal length and enumeration of hypertrees |
| 1500-1520 | M. Mitjana Weakly distance-regular digraphs P. Chebotarev Out forests of a digraph, the Kirchhoff matrix,and Markov chain probabilities |
| 1530-1550 | M. Klin A computational approach to partial difference sets |
| 1620-1720 | B.
Shader Spectra of Tournaments |
Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts
| Tuesday 10 July | |
| 0930-1030 | P. W.
Fowler Eigenvalues at work in chemistry: fullerenes as graphs and molecules |
| 1100-1130 | R. King Automorphism groups and spectra of highly symmetrical graphs |
| 1140-1210 | K. Taylor Spectra of block Toeplitz matrices D. Olesky Digraphs with large exponent |
| 1430-1450 | D. Stevanovic Constructing fullerene graphs from their eigenvalues and angles M. Lang Bipartite distance-regular graphs and representation diagrams |
| 1500-1520 | D. Mojdeh Graphs, codes and their applications |
| 1530-1550 | I. Kovacs Some applications of the discrete Fourier transformation in graph theory |
| 1620-1720 | P.
Hansen Computers 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. Bielak The zeros of chromatic polynomials of graphs M. Muzychuk Isomorphism problem for circulants |
| 1140-1210 | C. Cerf Graphs of knots and links P. Cara Incidence geometry and graphs |
Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts
| Thursday 12 July | |
| 0930-1030 | D.
Cvetkovic Graphs with least eigenvalue -2 |
| 1100-1150 | P. Rowlinson A survey of star complements |
| 1200-1220 | I. Sciriha Polynomial reconstruction for a class of disconnected graphs W. Korczynski On a presentation of graphs |
| 1430-1450 | M. Lepovic Some results on graphs with exactly two main eigenvalues R. Whitty Diagonalising the Laplacian of a directed tree |
| 1500-1520 | D. Bokal Embedding cartesian products of graphs by using eigenvectors of Laplacian matrix K. Markstrom Isomagnetic Graphs |
| 1530-1550 | N. Abreu & C.
Oliviera The characteristic polynomial of the Laplacian of (a,b)-linear class of graphs L. Hellstrom How many steps does the Gauss-Jordan elimination require? |
| 1620-1720 | B.
Mohar Minor monotone spectral invariants of graphs |
Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts
| Friday 13 July | |
| 0930-1030 | M. A.
Fiol Spectral 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. Jorgensen Directed strongly regular graphs, construction and non-existence |
| 1530-1630 | P. J.
Cameron Strongly 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
B SHADER
Spectra of Tournaments
Recent results and open problems related to the spectra of tournament matrices (i.e. (0,1)-matrices A satisfying A+A^T=J-I), will be surveyed. Topics will include the relationship between tournament matrices and biclique partitions of the complete graph, the largest eigenvalue of a tournament matrix and ranking players in a round-robin tournament, and the spectral properties of tournament matrices over finite fields.
Top | Monday | Tuesday | Wednesday | Thursday | Friday | Abstracts