LARGE PLANAR GRAPHS WITH GIVEN DIAMETER AND MAXIMUM DEGREE

Authors
FELLOWS M HELL P SEYFFARTH K
Citation
M. Fellows et al., LARGE PLANAR GRAPHS WITH GIVEN DIAMETER AND MAXIMUM DEGREE, Discrete applied mathematics, 61(2), 1995, pp. 133-153
Citations number
6
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
61
Issue
2
Year of publication
1995
Pages
133 - 153
Database
ISI
SICI code
Abstract
We consider the problem of determining the maximum number of vertices in a planar graph with given maximum degree Delta and diameter k. This number has previously been exactly determined when k = 2. We show her e that when k = 3, the number is roughly between 4.5 Delta and 8 Delta . We also show that in general the number is Theta(Delta([k/2])) for a ny fixed value of k.