The degree/diameter problem in maximal planar bipartite graphs

Visualitza/ Obre
Data de publicació
2016Citació recomanada
Dalfó, Cristina;
Huemer, Clemens;
Salas Piñón, Julián;
.
(2016)
.
The degree/diameter problem in maximal planar bipartite graphs.
Electronic Journal of Combinatorics, 2016, vol. 23, núm. 1.
https://doi.org/10.37236/4468.
Metadades
Mostra el registre d'unitat completResum
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.