The Open UniversitySkip to content

Moore graphs and beyond: A survey of the degree/diameter problem

Miller, M and Širáň, Jozef (2013). Moore graphs and beyond: A survey of the degree/diameter problem. Electronic Journal of Combinatorics (Dynamic Surveys) pp. 1–92.

Google Scholar: Look up in Google Scholar


The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter.

General upper bounds - called Moore bounds - for the order of such graphs and digraphs are attainable only for certain special graphs and digraphs. Finding better (tighter) upper bounds for the maximum possible number of vertices, given the other two parameters, and thus attacking the degree/diameter problem 'from above', remains a largely unexplored area. Constructions producing large graphs and digraphs of given degree and diameter represent a way of attacking the degree/diameter problem 'from below'.

This survey aims to give an overview of the current state-of-the-art of the degree/diameter problem. We focus mainly on the above two streams of research. However, we could not resist mentioning also results on various related problems. These include considering Moore-like bounds for special types of graphs and digraphs, such as vertex-transitive, Cayley, planar, bipartite, and many others, on the one hand, and related properties such as connectivity, regularity, and surface embeddability, on the other hand.

Item Type: Journal Item
ISSN: 1077-8926
Project Funding Details:
Funded Project NameProject IDFunding Body
Not SetARC DP0450294Australian Research Council
Not SetNot SetSlovak Research Grant Agencies VEGA and APVT.
Marie Curie International Incoming Fellowship within the 7th European Community Framework ProgrammeNot SetEU
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 41753
Depositing User: Jozef Širáň
Date Deposited: 19 Jan 2015 15:31
Last Modified: 07 Dec 2018 10:28
Share this page:

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU