Large planar graphs with given diameter and maximum degree
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\).
scientific article; zbMATH DE number 790496