logo

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. 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
Back to ICMS Website