The degree/diameter problem in maximal planar bipartite graphs
MetadataShow full item record
The (∆, D) (degree/diameter) problem consists of finding the largest possiblenumber of verticesnamong all the graphs with maximum degree ∆ and diameter D. We consider the (∆, D) problem for maximal planar bipartite graphs, that is,simple planar graphs in which every face is a quadrangle. We obtain that for the (∆,2) problem, the number of vertices is n= ∆ + 2; and for the (∆,3) problem, n= 3∆−1 if ∆ is odd and n= 3∆−2 if ∆ is even. Then, we prove that, for the general case of the (∆, D) problem, an upper bound on n is approximately 3(2D+ 1)(∆−2) [D/2], and another one is C(∆−2) [D/2] if ∆>D and C is a sufficiently large constant. Our upper bounds improve for our kind of graphs theone given by Fellows, Hell and Seyffarth for general planar graphs. We also givea lower bound onnfor maximal planar bipartite graphs, which is approximately (∆−2)D/2 if D is even, and 3(∆−3)D/2 if D is odd, for ∆ and D sufficiently largein both cases.