Dear all,

Today at 14.00 PhD students Grahame Erskine and Rob Lewis will present some of the results from their MSc dissertations.

Title: Cayley graphs in the degree-diameter problem

Abstract: In this talk we will present some results of the work for our recent M840 dissertations in algebraic graph theory, which both investigated aspects of the degree-diameter problem related to Cayley graphs. We begin with an introduction and basic results for the degree-diameter problem and Cayley graphs. We then discuss the methods and results from a large computer search for "interesting" graphs.

Circulant graphs, defined as having circulant matrices as their adjacency matrices, may be considered as Cayley graphs of cyclic groups and so are one of the simplest categories of graphs for exploring the degree-diameter problem. In the literature, the question of the size of an extremal circulant graph of arbitrary diameter has only been answered for degree up to 5. In 2004 Dougherty and Faber presented "best" constructions for degree 6 and 7 that have been proven extremal by computer search for a limited range of diameters. Following a similar approach, new constructions for degree 8 and 9 are presented along with an existence proof for degree 8 for all diameters. We will also discuss the intimate relation between these "best" graphs and some lower and upper bounds by Chen & Jia and Dougherty & Faber, including asymptotic formulae for their size and also the structure of their distance partitions. We also note the discovery that these graphs all have odd girth 2k+1 where k is the diameter. Conjectures are presented which should help in the search for families of extremal circulant graphs of arbitrary diameter with higher degree.

The talk will be held in the usual place, room 306 of the Alan Turing Building.

Best wishes,

Ian
-- The Open University is incorporated by Royal Charter (RC 000391), an exempt charity in England & Wales and a charity registered in Scotland (SC 038302).