School Seminars and Colloquia

The Degree-Diameter Problem: A Few Results and a Wealth of Open Problems

Discrete Structures and Algorithms (Seminar)

by Guillermo Pineda-Villavicencio, University of Ballarat

Institution: Mathematics and Statistics
Date: Fri 12th March 2010
Time: 1:00 PM
Location: room 306, Alice Hoy Building

Abstract: The Degree-Diameter Problem asks for the largest graph with given maximum degree and diameter. In joint work with Eyal Loz (University of Auckland) and Hebert Perez-Roses (The University of Newcastle), we have recently constructed the largest known graphs of maximum degree in [17,20] and diameter in [2,10]. A wide range of techniques and concepts were used, such as graph compounding, vertex duplication, Kronecker product, polarity graphs and voltage graphs. Among the techniques employed, we believe voltage graphs are the leading beacon for future directions in the construction of large graphs. However, many weaknesses need to be tackled to reach their potential. For instance,
(i) There is no methodology to obtain voltage groups and voltage assignments to generate graphs with specific properties.
(ii) The procedure is done "blindly" in the sense that little is known about the classes of graphs that can be lifted.
In this talk we present a number of ideas and open problems that address these defects.

For More Information: For more information contact Dr. David Wood: