English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/132344
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:

The degree/diameter problem in maximal planar bipartite graphs

AuthorsDalfo, Cristina; Huemer, Clemens; Salas, Julian
KeywordsMaximal planar bipartite graphs
Δ, D problem
Issue Date2014
CitationElectronic Notes in Discrete Mathematics 46: 73- 80 (2014)
Abstract© 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.
Identifiersdoi: 10.1016/j.endm.2014.08.011
issn: 1571-0653
Appears in Collections:(IIIA) Artículos
Files in This Item:
File Description SizeFormat 
accesoRestringido.pdf15,38 kBAdobe PDFThumbnail
Show full item record
Review this work

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.