English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/132344
Compartir / Impacto:
Estadísticas
Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Título

The degree/diameter problem in maximal planar bipartite graphs

AutorDalfo, Cristina; Huemer, Clemens; Salas, Julian
Palabras claveMaximal planar bipartite graphs
Δ, D problem
Fecha de publicación2014
EditorElsevier
CitaciónElectronic Notes in Discrete Mathematics 46: 73- 80 (2014)
Resumen© 2014 Elsevier B.V. The (δ, D) (degree/diameter) problem consists of finding the largest possible number of vertices n among all the graphs with maximum degree δ and diameter D. We consider the (δ, D) problem for maximal planar bipartite graphs, that are 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 study the general case (δ, D) and obtain that 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 bound improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on n for maximal planar bipartite graphs, which is approximately (δ-2)k if D=2k, and 3(δ-3)k if D=2k+1, for δ and D sufficiently large in both cases.
URIhttp://hdl.handle.net/10261/132344
DOI10.1016/j.endm.2014.08.011
Identificadoresdoi: 10.1016/j.endm.2014.08.011
issn: 1571-0653
Aparece en las colecciones: (IIIA) Artículos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
accesoRestringido.pdf15,38 kBAdobe PDFVista previa
Visualizar/Abrir
Mostrar el registro completo
 


NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.