Large planar graphs with given diameter and maximum degree (Q1897359): Difference between revisions

Let \(G\) be a planar graph on \(n\) vertices with maximum degree \(\Delta\) and diameter \(k\). The problem of determining the maximum number of vertices that \(G\) can have is studied in this paper. When \(k= 2\), it has been shown that \(n\leq \lfloor{3\over 2}\Delta\rfloor+ 1\) (for \(\Delta\geq 8\)). In this paper, the authors show that when \(k= 3\), we have \(\lfloor {9\over 2} \Delta\rfloor- 3\leq n\leq 8\Delta+ 12\). They also show that in general \(n\) is \(\Theta(\Delta^{\lfloor k/2\rfloor})\) for any fixed value of \(k\).