✦ LIBER ✦
Extremal graphs of diameter two and given maximum degree, embeddable in a fixed surface
✍ Scribed by Knor, Martin; ?ir�?, Jozef
- Publisher
- John Wiley and Sons
- Year
- 1997
- Tongue
- English
- Weight
- 137 KB
- Volume
- 24
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
It is known that for each d there exists a graph of diameter two and maximum degree d which has at least (d/2) (d + 2)/2 vertices. In contrast 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 ≥ d S , which is embeddable in S, has at most (3/2)d + 1 vertices. Moreover, this upper bound is best possible, and we show that extremal graphs can be found among surface triangulations.