## File(s) under permanent embargo

# The degree-diameter problem for sparse graph classes

Version 2 2024-06-05, 04:40

Version 1 2019-06-25, 11:37

journal contribution

posted on 2024-06-05, 04:40 authored by Guillermo Pineda VillavicencioGuillermo Pineda Villavicencio, DR Woodf DavidThe degree-diameter problem asks for the maximum number of vertices in a graph with maximum degree Δ and diameter k. For fixed k, the answer is Ө(Δ

^{k}). We consider the degree-diameter problem for particular classes of sparse graphs, and establish the following results. For graphs of bounded average degree the answer is Ө(Δ^{[k-1]}), and for graphs of bounded arboricity the answer is Ө(Δ^{[k/2]}), in both cases for fixed k. For graphs of given treewidth, we determine the the maximum number of vertices up to a constant factor. Other precise bounds are given for graphs embeddable on a given surface and apex-minor-free graphs.