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.
@article{10_37236_4313,
author = {Guillermo Pineda-Villavicencio and David R. Wood},
title = {The degree-diameter problem for sparse graph classes},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {2},
doi = {10.37236/4313},
zbl = {1327.05292},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4313/}
}
TY - JOUR
AU - Guillermo Pineda-Villavicencio
AU - David R. Wood
TI - The degree-diameter problem for sparse graph classes
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/4313/
DO - 10.37236/4313
ID - 10_37236_4313
ER -
%0 Journal Article
%A Guillermo Pineda-Villavicencio
%A David R. Wood
%T The degree-diameter problem for sparse graph classes
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/4313/
%R 10.37236/4313
%F 10_37236_4313
Guillermo Pineda-Villavicencio; David R. Wood. The degree-diameter problem for sparse graph classes. The electronic journal of combinatorics, Tome 22 (2015) no. 2. doi: 10.37236/4313
