Universitat de Lleida
    • English
    • català
    • español
  • español 
    • English
    • català
    • español
  • Iniciar sesión
Repositori Obert UdL
Ver ítem 
  •   Inicio
  • Recerca
  • Matemàtica
  • Articles publicats (Matemàtica)
  • Ver ítem
  •   Inicio
  • Recerca
  • Matemàtica
  • Articles publicats (Matemàtica)
  • Ver ítem
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
Ver/Abrir
Article (431.4Kb)
Fecha de publicación
2016
Autor/a
Dalfó, Cristina
Huemer, Clemens
Salas Piñón, Julián
Cita recomendada
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.
Impacto


Logo de Web of Science    citaciones en Web of Science

Logo de Scopus    citaciones en Scopus

Logo de Google Académico  Google Académico
Compartir
Exportar a Mendeley
Metadatos
Mostrar el registro completo del ítem
Resumen
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
Es parte de
Electronic Journal of Combinatorics, 2016, vol. 23, núm. 1
Proyectos de investigación europeos
Colecciones
  • Articles publicats (Matemàtica) [358]
  • Publicacions de projectes de recerca del Plan Nacional [2953]

Contacto | Sugerencias | Aviso legal
© 2023 BiD. Universitat de Lleida
Metadatos sujetos a 
 

 

Explorar

Todo el repositorioComunidades y coleccionesPor fecha de publicaciónAutoresTítulosMateriasEsta colecciónPor fecha de publicaciónAutoresTítulosMaterias

Estadísticas

Ver Estadísticas de uso

De interés

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

Contacto | Sugerencias | Aviso legal
© 2023 BiD. Universitat de Lleida
Metadatos sujetos a