Moore graphs and beyond: a survey of the degree/diameter problem
From MaRDI portal
Publication:2583309
Summary: 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.
Recommendations
Cited in
(only showing first 100 items - show all)- On bipartite graphs of defect 2
- On large vertex-symmetric digraphs
- Graphs of given degree and diameter obtained as abelian lifts of dipoles
- On the existence of graphs of diameter two and defect two
- Constructions of Hamiltonian graphs with bounded degree and diameter \(O(\log n)\)
- Eulogy for Professor Mirka Miller (1949--2016)
- On the defect of vertex-transitive graphs of given degree and diameter
- Distant set distinguishing edge colourings of graphs
- On the excess of vertex-transitive graphs of given degree and girth
- The dual diameter of triangulations
- On digraphs of excess one
- On diregular digraphs with degree two and excess two
- Digraphs with degree two and excess two are diregular
- Constructing goal-minimally k-diametric graphs by lifts
- Large Cayley graphs of small diameter
- Distant sum distinguishing index of graphs
- On diregular digraphs with degree two and excess three
- Greedy routing in circulant networks
- On new record graphs close to bipartite Moore graphs
- On networks with order close to the Moore bound
- The average distance and the diameter of dense random regular graphs
- On the packing chromatic number of Moore graphs
- A lower bound for the discriminant of polynomials related to Chebyshev polynomials
- A connection between a question of Bermond and Bollobás and Ramanujan graphs
- On graphs of defect at most 2
- A spectral version of the Moore problem for bipartite regular graphs
- Approximate Moore graphs are good expanders
- On total regularity of mixed graphs with order close to the Moore bound
- Rainbow connectivity using a rank genetic algorithm: Moore cages with girth six
- On the combinatorial design of data centre network topologies
- KMcube: the compound of Kautz digraph and Möbius cube
- A survey on the missing Moore graph
- On the nonexistence of almost Moore digraphs
- Degree/diameter problem for trees and pseudotrees
- Brooks' theorem on powers of graphs
- On the sizes of expander graphs and minimum distances of graph codes
- Structural properties of Cayley digraphs with applications to mesh and pruned torus interconnection networks
- Distances of centroid sets in a graph-based construction for information security applications
- Distant set distinguishing total colourings of graphs
- Turán problems for \(k\)-geodetic digraphs
- Special structures in \(\mathcal{Q}(4, q)\), projective planes and its application in \(L(h, k)\)-colorings of their Moore graphs
- Nonexistence of almost Moore digraphs of degrees 4 and 5 with self-repeats
- On the maximum order of graphs embedded in surfaces
- Coloring powers and girth
- Mixed Moore Cayley graphs
- A revised Moore bound for mixed graphs
- Unitary graphs
- The degree-diameter problem for claw-free graphs and hypergraphs
- Smallest vertex-transitive graphs of given degree and diameter
- Moore graphs and cycles are extremal graphs for convex cycles
- Cayley graphs of diameter two with order greater than 0.684 of the Moore bound for any degree
- Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter
- New largest known graphs of diameter 6
- Ranking measures for radially Moore graphs
- On large ( , D, D, 1)-graphs
- scientific article; zbMATH DE number 5994744 (Why is no real title available?)
- A construction of large graphs of diameter two and given degree from abelian lifts of dipoles
- Large vertex-transitive and Cayley graphs with given degree and diameter
- Degree diameter problem on triangular networks
- Topology of interconnection networks with given degree and diameter
- scientific article; zbMATH DE number 4043895 (Why is no real title available?)
- Distant irregularity strength of graphs
- Cayley graphs of diameter two and any degree with order half of the Moore bound
- KCube: a novel architecture for interconnection networks
- Approaching the Moore bound for diameter two by Cayley graphs
- Radial Moore graphs of radius three
- The maximum degree and diameter-bounded subgraph in the mesh
- Large circulant graphs of fixed diameter and arbitrary degree
- Degree diameter problem on honeycomb networks
- The degree-diameter problem for circulant graphs of degree 8 and 9
- The degree-diameter problem for sparse graph classes
- Inequality and network formation games
- Degree diameter problem on silicate network
- Plane graphs with large faces and small diameter
- scientific article; zbMATH DE number 7378741 (Why is no real title available?)
- t-strong cliques and the degree-diameter problem
- scientific article; zbMATH DE number 7471110 (Why is no real title available?)
- On the automorphisms of a family of small q-regular graphs of girth 8
- Series of families of degree six circulant graphs
- Algebraic and computer-based methods in the undirected degree/diameter problem - A brief survey
- Some new large (Δ, 3)‐graphs
- A note on degree/diameter monotonicity of digraphs
- A note on the degree-diameter problem for arc-transitive graphs
- Smallest regular graphs of given degree and diameter
- scientific article; zbMATH DE number 6277698 (Why is no real title available?)
- New improvements on connectivity of cages
- Acyclic, star, and injective colouring: bounding the diameter
- Lower Bounds on Lattice Covering Densities of Simplices
- On girth-biregular graphs
- Large bipartite Cayley graphs of given degree and diameter
- Non-existence of bipartite graphs of diameter at least \(4\) and defect \(2\)
- Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups
- Large Cayley digraphs of given degree and diameter
- Product structure of graph classes with bounded treewidth
- Weighted cages
- Minimum 2-percolating sets in 2-connected, diameter 2 graphs
- Edge-disjoint Hamilton cycles in the McKay-Miller-Širáň graphs
- A proof of a version of Griggs and Yeh's conjecture for L (2, 1)-labeling of iterated Mycielskians
- New results regarding the permutation cycle structure of almost Moore digraphs
- Improvements in nonlocal metric dimension bounds
This page was built for publication: Moore graphs and beyond: a survey of the degree/diameter problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2583309)
