|Title: Recent Advances and Open Problems in the Degree/Diameter Problem|
|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, firstname.lastname@example.org|
|Date: 2014-10-20 at 4:00PM|
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.
See All Seminars