The degree-diameter problem for sparse graph classes (Q491538): Difference between revisions

Summary: The degree-diameter problem asks for the maximum number of vertices in a graph with maximum degree \(\Delta\) and diameter \(k\). For fixed \(k\), the answer is \(\Theta(\Delta^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 \(\Theta(\Delta^{k-1})\), and for graphs of bounded arboricity the answer is \(\Theta(\Delta^{\lfloor k/2\rfloor})\), in both cases for fixed \(k\). For graphs of given treewidth, we determine 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.