On the maximum order of graphs embedded in surfaces

The maximum number of vertices in a graph of maximum degree Δ≥3Δ≥3 and fixed diameter k≥2k≥2 is upper bounded by (1+o(1))(Δ−1)k(1+o(1))(Δ−1)k. If we restrict our graphs to certain classes, better upper bounds are known. For instance, for the class of trees there is an upper bound of (2+o(1))(Δ−1)⌊k/2⌋(2+o(1))(Δ−1)⌊k/2⌋ for a fixed k. The main result of this paper is that graphs embedded in surfaces of bounded Euler genus g behave like trees, in the sense that, for large Δ, such graphs have orders bounded from above by{c(g+1)(Δ−1)⌊k/2⌋if k is evenc(g3/2+1)(Δ−1)⌊k/2⌋if k is odd, where c is an absolute constant. This result represents a qualitative improvement over all previous results, even for planar graphs of odd diameter k. With respect to lower bounds, we construct graphs of Euler genus g, odd diameter k  , and order c(g+1)(Δ−1)⌊k/2⌋ for some absolute constant c>0c>0. Our results answer in the negative a question of Miller and Širáň (2005).