School Seminars and Colloquia

Some new results on the degree-diameter and the degree-girth problems, both asymptotic and non-existential

Discrete Structures and Algorithms (Seminar)

by Guillermo Pineda-Villavicencio


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: woodd@unimelb.edu.au