Maximum/minimum orders of graphs with given degree and given diameter and/or girth

Datum / Date: 22.4.25
Čas / Time: 13:00-14:00
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Marston Conder (University of Auckland)
Naslov / Title: Maximum/minimum orders of graphs with given degree and given diameter and/or girth
Povzetek / Abstract:

The well-known Moore graphs (including odd-length cycles, the complete graphs, the Petersen graph and the Hoffman-Singleton graph) are regular graphs of maximum conceivable order with given degree and diameter, or equivalently, regular graphs of minimum conceivable order with given degree and girth (sometimes called cages), according to the well-known Moore bound.  

More generally, the task of finding the largest regular graph with given degree and diameter is called the degree-diameter problem, and the corresponding one for given degree and girth is called the cage problem. Various people in the combinatorial community have contributed answers or partial answers to these problems.

At a BIRS workshop at Banff in May 2023, some investigations were made into the stronger notion of a degree-diameter-girth problem, namely finding the largest regular graph with given degree, diameter and girth.  I will report on some of what was discovered, after reviewing some of the background to the degree-diameter and cage problems.

Delite z drugimi

Orodna vrstica za dostopnost

Politika zasebnosti / Privacy Overview

Ta spletna stran uporablja piškotke, da vam lahko zagotovi najboljšo možno uporabniško izkušnjo. Informacije o piškotkih se shranjujejo v vašem brskalniku in omogočajo funkcije, kot je prepoznavanje ob vašem ponovnem obisku spletne strani, ter pomagajo naši ekipi razumeti, kateri deli spletne strani so za vas najbolj zanimivi in uporabni.


This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.