Show simple item record

dc.contributor.authorDalfó, Cristina
dc.contributor.authorHuemer, Clemens
dc.contributor.authorSalas Piñón, Julián
dc.date.accessioned2021-12-15T12:06:25Z
dc.date.available2021-12-15T12:06:25Z
dc.date.issued2016
dc.identifier.issn1077-8926
dc.identifier.urihttp://hdl.handle.net/10459.1/72566
dc.description.abstractThe (∆, 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.ca_ES
dc.description.sponsorshipResearch supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund under project MTM2014-60127-P, and by the Catalan Research Council under project 2014SGR1147.ca_ES
dc.language.isoengca_ES
dc.publisherElectronic Journal of Combinatoricsca_ES
dc.relationinfo:eu-repo/grantAgreement/MINECO//MTM2014-60127-P/ES/TECNICAS DE OPTIMIZACION EN TEORIA DE GRAFOS, GRUPOS Y COMBINATORIA. APLICACIONES A REDES, ALGORITMOS Y PROTOCOLOS DE COMUNICACION/ca_ES
dc.relation.ispartofElectronic Journal of Combinatorics, 2016, vol. 23, núm. 1ca_ES
dc.rights(c) Dalfó et al., 2016ca_ES
dc.subjectGraph theoryca_ES
dc.subjectDegree/diameter problemca_ES
dc.subjectPlanar bipartite graphsca_ES
dc.titleThe degree/diameter problem in maximal planar bipartite graphsca_ES
dc.typeinfo:eu-repo/semantics/articleca_ES
dc.identifier.idgrec028004
dc.rights.accessRightsinfo:eu-repo/semantics/openAccessca_ES
dc.identifier.doihttps://doi.org/10.37236/4468


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record