Some new results on the degree-diameter and the degree-girth problems, both asymptotic and non-existential
by Guillermo Pineda-Villavicencio
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