Department Seminars and Colloquia
Some new results on the degree-diameter and the degree-girth problems, both asymptotic and non-existentialDiscrete Structures and Algorithms Seminar
Institution: University of Ballarat
Date: Thu 26th August 2010
Time: 2:00 PM
Location: Old Geology 1, The University of Melbourne
Abstract: The degree-diameter problem aims to find the largest possible order of a graph with given degree and diameter, while the degree-girth problem aims to find the smallest possible order of a graph with given degree and girth. In this context the Moore bound constitutes both an upper bound on the order of a graph of given maximum degree and diameter, and a lower bound on the order of a graph of given minimum degree and odd girth.
Graphs missing or exceeding the Moore bound by e are called graphs with defect or excess e, respectively. With the exception of the degree 57 and diameter 2, Moore graphs have been fully characterized, so have been the graphs with defect or excess 1. However, graphs with defect or excess 2 represent a wide unexplored area. In the talk I present both asymptotic and non-existentence results on the class of graphs with defect or excess 2.
Joint work with Charles Delorme (UniversitÃ© Paris-Sud)
For More Information: contact: David Wood. email: email@example.com