Moore Graphs and Beyond: A survey of the Degree/Diameter Problem
By Mirka Miller, Jozef Sirán. 2013
378 citations recorded by the source corpus.
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.
Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Electrical and Electronic Engineering
View Paper: https://www.semanticscholar.org/paper/2dd8c1b9473bfe7a4a23902b78669d6a762f928c
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Computer Networks and Communications
In Electrical and Electronic Engineering
Citations in the corpus
- Slim Fly: A Cost Effective Low-Diameter Network Topology (2014, methodology): “Finally, the introduced approach for optimizing networks using the Moore Bound can be extended for higher-diameter networks which, while providing slightly higher latency, could establish scalable structures allowing for millions of endpoints.”