On the maximum order of graphs embedded in surfaces

Eran Nevo, Guillermo Pineda-Villavicencio, David R. Wood

The maximum number of vertices in a graph of maximum degree $\Delta \ge 3$ and fixed diameter $k\ge 2$ is upper bounded by $(1+o(1))(\Delta -1{)}^k$. If we restrict our graphs to certain class…