On the maximum order of graphs embedded in surfaces

Abstract

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 classes, better upper bounds are known. For instance, for the class of trees there is an upper bound of $(2+o(1))(\Delta -1{)}^{\lfloor k/2\rfloor }$ 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 $\Delta$, such graphs have orders bounded from above by \[begin{cases} c(g+1)(Δ-1)^{\lfloor k/2\rfloor} & \text{if $k$ is even} c(g^{3/2}+1)(Δ-1)^{\lfloor k/2\rfloor} & \text{if $k$ is odd}, \{cases}\] 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(\sqrt{g}+1)(\Delta -1{)}^{\lfloor k/2\rfloor }$ for some absolute constant $c>0$. Our results answer in the negative a question of Miller and Širáň (2005).

13 pages, 3 figures

Cited by in corpus (1)

• The degree-diameter problem for sparse graph classes