Electronic Journal of Graph Theory and Applications 13 .
, 211Ae215 New results on the degree-diameter problem for undirected graphs Francesc Comellas Departament de MatemaAtiques.
Campus del Baix Llobregat.
Universitat PoliteAcnica de Catalunya.
Esteve Terradas 5.
Castelldefels (Barcelon.
Catalonia.
Spain comellas@upc.
Abstract This paper presents fourteen newly discovered largest undirected graphs with specified degree and diameter, identified since the publication of the comprehensive survey by M.
Miller and J.
SUiraAnU (Electron.
Combin.
DS14, 2nd.
May 2.
These findings advance the longstanding investigation of the degree-diameter problem, a key topic in graph theory, and offer a fresh insight for both theoretical research and practical applications in network design and combinatorial Keywords: large Graphs, degree-diameter problem.
Cayley graphs Mathematics Subject Classification : 05C88, 05C89 DOI: 10.
5614/ejgta.
Introduction The construction of graphs with the largest possible order for a given maximum degree and diameter, known as the (OI.
D)-problem, is a question of particular interest in graph theory.
This problem receives much attention due to its implications in the design of topologies in interconnection networks and its relevance to issues such as data alignment and the description of some cryptographic protocols.
Additionally, the (OI.
D)-problem relates to various graph properties, including regularity, connectivity, and cycle structure.
Received: 8 December 2024.
Revised: 26 March 2025.
Accepted: 2 April 2025.
New results on the degree-diameter problem for undirected graphs Francesc Comellas.
Hoffman and Singleton introduced the concept of Moore graphs .
, and proved that the largest possible order of a graph with maximum degree OI (OI > .
and diameter D is bounded by OI(OI Oe .
D Oe 2 1 OI OI(OI Oe .
A A A OI(OI Oe .
DOe1 = = n(OI.
D) OIOe2 This value is called the Moore bound, and a graph attaining it is known as a Moore graph.
Different authors have proved that for D Ou 2 and OI Ou 3, there can only exist Moore graphs for D = 2 and OI = 3, 7 and 57.
For the first two cases the graphs are unique and are, respectively, the PetersenAos graph on 10 vertices and the HoffmanAeSingletonAos graph on 50 vertices.
The existence of a Moore graph for D = 2 and OI = 57 is not known.
Thus, it is of interest to find graphs which for a given diameter and maximum degree, have a number of vertices as close as possible to the Moore bound, which are known as (OI.
D) graphs.
The (OI.
D) problem for undirected graphs has been approached in different ways.
It is possible to give bounds to the order of the graphs for a given maximum degree and diameter.
On the other hand, as the theoretical bounds are difficult to attain, most of the work deals with the construction of graphs that, for this given diameter and maximum degree, have a number of vertices as close as possible to the theoretical bounds.
Different techniques have been developed depending on the way graphs are generated and their parameters are calculated.
Roughly half of the largest graphs for maximum degrees from 3 to 16 and maximum diameters from 2 to 10, correspond to Cayley graphs obtained from semidirect products of cyclic groups and have been found by computer methods .
, 9, .
The computer is used for generating the graphs and testing for the desired properties.
Compounding is another technique that has proven useful in producing (OI.
D) graphs.
This technique generalizes a method introduced by Quisquater .
, which involves replacing a single vertex in a bipartite Moore graph with a complete graph.
GoAmez.
Fiol and Serra .
further modified this technique to replace several vertices of a given graph with another graph or copies of a graph, rearranging the edges appropriately .
ee also .
Compound graphs have been a basic tool in constructing many large (OI.
D) graphs, particularly for small diameters.
Other large graphs have been found as graph products or from particular methods.
New results In this section we give the details of twelve new largest (OI.
D) graphs found by the author and two new graphs by other authors that were communicated to us but have not been published.
Since the publication of the review by M.
Miller and J.
SUiraAnU .
, .
, there are two other new entries that have been pubished elsewhere: .
, .
= 200 by M.
Abas .
, .
= 1697688 by A.
Rodriguez .
The adjacency lists for the new results as well as information .
uthor, details of the construction, adjacency lists, etc.
) for most degree-diameter graphs with order less than 20000, can be downloaded from .
Addition of vertices Vlad Pelekhaty .
obtained in 2021 the .
, .
= 856 new largest graph from the graph Q8 d with degree 13, diameter 3 and 851 vertices described in .
by adding five new vertices New results on the degree-diameter problem for undirected graphs Francesc Comellas.
and reconnecting several vertices.
The resulting graph is regular, has girth 3 and average distance The adjacency list can be downloaded from .
Constructions based on a symmetric graph.
Jianxiang Chen .
obtained in 2018 a new largest .
, .
graph with 360 vertices.
This graph is derived from the symmetric Foster graph on 144 vertices with diameter 7 and girth 8 as follows:
Let G be the symmetric graph and O a complete pairing relation on its edges.
The new graph.
H, is constructed as follows: The vertex set of H is V (G) O E(G).
If v OO V (G) and u OO V (G), then they are not connected in H.
If v OO V (G) and u OO E(G), then they are connected in H iff v is incident to u in G.
If v OO E(G) and u OO E(G), then they are connected in H iff v O u by the pairing relation.
The graph H is not a Cayley graph.
It is regular with girth 13 and has average The SageMath program that produces the graph and the adjacency list can be downloaded from .
Following a similar process, we can obtain the .
, .
= 70 largest degree-diameter graph .
from the Coxeter graph of 28 vertices with diameter 4 and girth 5.
The SageMath program that produces this graph and more details can be found in .
Cayley graphs from semidirect product of cyclic groups Cayley graphs are strong candidates for the degree-diameter problem due to their highly symmetric nature.
As vertex-transitive graphs, all vertices play identical structural role, simplifying both computational searches and diameter calculations.
From a computer science perspective, vertex transitivity offers another key advantage: it enables simpler network architectures.
Since all nodes are structurally equivalent, networks can use uniform processors and routing algorithms, streamlining design and implementation.
Let G be a finite group and S a generating subset of G that does not contain the identity The Cayley graph of G with respect to S is the directed graph whose vertex set consists of the elements of G, with an edge set given by E = {.
, .
= xs, for some s OO S}.
If S is closed under inverses, then .
, .
OO E if and only if .
, .
OO E, making the graph undirected.
The particular family of Cayley graphs considered here is based on the semidirect product of cyclic groups, introduced by M.
Dinneen and P.
Hafner in the context of the degree-diameter problem .
Given cyclic groups Zm and Zn if a multiplicative unit a OO Zn divides m, the semidirect product ZmUOa Zn can be defined using the multiplication rule .
, .
, .
= .
u mod m, yau v mod .
If the generating set of the group is closed under inversion, the resulting Cayley graph is undirected.
The semidirect product allows for the construction of nonabelian groups that are larger and more complex than simple cyclic or direct product groups.
This means that Cayley graphs derived from such groups, with an appropriate choice of generators, can optimize connectivity .
, minimize diamete.
while supporting more vertices and maintaining the degree determined by the generators, crucial requirements for the degree-diameter problem.
The search for optimal Cayley graphs with given degree and diameter is conducted via a randomized exploration of generating sets.
A C program, originally developed by the author in 1994 to generate the graph .
, .
= 253 from the group associated with the semidirect product Z11 UO9 Z23 .
New results on the degree-diameter problem for undirected graphs Francesc Comellas.
has been used to construct the new Cayley graphs presented in the following table.
The program is available for download at .
(OI.
, .
76 891 Z17 UO4359 Z4523
,3.
, .
Z24 UO90 Z511
, .
Z20 UO970 Z2651
,2.
,1.
,1.
, .
Z15 UO267 Z341
, .
Z40 UO24 Z41
, .
Z9 UO44 Z259
, .
Z81 UO22 Z163
, .
, .
, .
, .
, .
Z36 UO434 Z545
, .
, .
, .
,116 ], .
, .
, .
29 621 Z19 UO1205 Z1559
, .
, .
, .
, .
, .
,1.
, .
Z24 UO362 Z1687
,1.
, .
,1.
, .
,1.
, .
, .
,1.
, .
,1.
, .
,1.
, .
Z45 UO191 Z1291
, .
, .
, .
, .
, .
, .
, .
Z48 UO772 Z1615
,1.
,1.
,1.
Conclusions In this work, we presented contributions to the degree-diameter problem for undirected graphs by introducing fourteen new largest graphs with specified maximum degree and diameter.
These results extend the known catalog of optimal and near-optimal graphs, which are of interest for both theoretical exploration and practical applications, such as network topology design.
The methodologies employed include adding vertices to existing graphs, constructing new graphs derived from well-known symmetric graphs, and utilizing semidirect products to discover large Cayley graphs by computer search.
Future research may focus on refining these techniques, in particular constructions based on symmetric graphs.
Acknowledgement The author gratefully acknowledges Jianxiang Chen and Vlad Pelekhaty for their willingness to share the details of their constructions.
References