MATH Seminar

Title: Recent Advances and Open Problems in the Degree/Diameter Problem
Seminar: Combinatorics
Speaker: Mirka Miller of Department of Mathematics, University of West Bohemia, Pilsen, Czech Republic; and School of Mathematical and Physical Sciences, University of Newcastle, Australia
Contact: Vojtech Rodl, rodl@mathcs.emory.edu
Date: 2014-10-20 at 4:00PM
Venue: W302
Download Flyer
Abstract: The degree/diameter problem is to find the largest possible graphs in terms of the number of vertices, given the maximum degree and diameter. The directed version is similar except that instead of the maximum degree constraint we are given the maximum out-degree. For both the undirected and directed versions of the problem there are general upper bounds on the number of vertices, called the Moore bounds. On the other hand, the best current lower bounds are obtained from constructions of ever larger graphs (given maximum degree and diameter).\\ \\ In this talk we will give an overview of the undirected, directed and mixed versions (allowing both undirected edges and directed arcs in the graph) of the problem and the most recent advances.\\ \\ The talk concludes with several open problems.