On the maximum order of graphs embedded in surfaces

Abstract: The maximum number of vertices in a graph of maximum degree

D e l t a g e 3

and fixed diameter

k g e 2

is upper bounded by

(1 + o (1)) (D e l t a - 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)) (D e l t a - 1)^{l f l o o r k / 2 f l o o r}

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

D e l t a

, such graphs have orders bounded from above by [begin{cases} c(g+1)(Delta-1)^{lfloor k/2 floor} & ext{if

k

is even} c(g^{3/2}+1)(Delta-1)^{lfloor k/2 floor} & ext{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 (s q r t g + 1) (D e l t a - 1)^{l f l o o r k / 2 f l o o r}

for some absolute constant

c > 0

. Our results answer in the negative a question of Miller and v{S}ir'av{n} (2005).

Recommendations

Cites work

Cited in

(10)

This page was built for publication: On the maximum order of graphs embedded in surfaces