EXTREMAL GRAPHS OF DIAMETER 2 AND GIVEN MAXIMUM DEGREE, EMBEDDABLE INA FIXED SURFACE

It is known that for each d there exists a graph of diameter two and m aximum degree d which has at least [(d/2)][(d + 2)/2] vertices. In con trast with this, we prove that for every surface S there is a constant d(S) such that each graph of diameter two and maximum degree d greate r than or equal to d(S), which is embeddable in S, has at most [(3/2)d ] + 1 vertices. Moreover, this upper bound is best possible, and we sh ow that extremal graphs can be found among surface triangulations. (C) 1997 John Wiley & Sons, Inc.