Universitat de Lleida
    • English
    • català
    • español
  • català 
    • English
    • català
    • español
  • Inicia la sessió
Repositori Obert UdL
Visualitza l'element 
  •   Inici
  • Recerca
  • Matemàtica
  • Articles publicats (Matemàtica)
  • Visualitza l'element
  •   Inici
  • Recerca
  • Matemàtica
  • Articles publicats (Matemàtica)
  • Visualitza l'element
JavaScript is disabled for your browser. Some features of this site may not work without it.

The degree/diameter problem in maximal planar bipartite graphs

Thumbnail
Visualitza/Obre
Article (431.4Kb)
Data de publicació
2016
Autor/a
Dalfó, Cristina
Huemer, Clemens
Salas Piñón, Julián
Citació 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.
Impacte


Logo de Web of Science    citacions a Web of Science

Logo d'Scopus    citacions a Scopus

Logo de Google Acadèmic  Google Acadèmic
Compartir
Exportar a Mendeley
Metadades
Mostra el registre d'unitat complet
Resum
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.
URI
http://hdl.handle.net/10459.1/72566
DOI
https://doi.org/10.37236/4468
És part de
Electronic Journal of Combinatorics, 2016, vol. 23, núm. 1
Projectes de recerca europeus
Col·leccions
  • Articles publicats (Matemàtica) [358]
  • Publicacions de projectes de recerca del Plan Nacional [2953]

Contacteu amb nosaltres | Envia comentaris | Avís legal
© 2023 BiD. Universitat de Lleida
Metadades subjectes a 
 

 

Explora

Tot el repositoriComunitats i col·leccionsPer data d'edicióAutorsTítolsMatèriesAquesta col·leccióPer data d'edicióAutorsTítolsMatèries

Estadístiques

Veure estadístiques d'ús

D'interès

Política institucional d'accés obertDiposita les teves publicacionsDiposita dades de recercaSuport a la recerca

Contacteu amb nosaltres | Envia comentaris | Avís legal
© 2023 BiD. Universitat de Lleida
Metadades subjectes a