The degree/diameter problem in maximal planar bipartite graphs (Q5890615)

Summary: The \((\Delta,D)\) (degree/diameter) problem consists of finding the largest possible number of vertices \(n\) among all the graphs with maximum degree \(\Delta\) and diameter \(D\).~We consider the \((\Delta,D)\) problem for maximal planar bipartite graphs, that is, simple planar graphs in which every face is a quadrangle.~We obtain that for the \((\Delta,2)\) problem, the number of vertices is \(n=\Delta+2\); and for the \((\Delta,3)\) problem, \(n= 3\Delta-1\) if \(\Delta\) is odd and \(n= 3\Delta-2\) if \(\Delta\) is even. Then, we prove that, for the general case of the \((\Delta,D)\) problem, an upper bound on \(n\) is approximately \(3(2D+1)(\Delta-2)^{\lfloor D/2\rfloor}\), and another one is \(C(\Delta-2)^{\lfloor D/2\rfloor}\) if \(\Delta\geqslant D\) and \(C\) is a sufficiently large constant. Our upper bounds improve for our kind of graphs the one given by \textit{M. Fellows} et al. [Discrete Appl. Math. 61, No. 2, 133--153 (1995; Zbl 0832.05060); Networks 32, No. 4, 275--281 (1998; Zbl 1002.90008)] for general planar graphs. We also give a lower bound on \(n\) for maximal planar bipartite graphs, which is approximately \((\Delta-2)^{k}\) if \(D=2k\), and \(3(\Delta-3)^k\) if \(D=2k+1\), for \(\Delta\) and \(D\) sufficiently large in both cases.