Universitat de Lleida
    • English
    • català
    • español
  • English 
    • English
    • català
    • español
  • Login
Repositori Obert UdL
View Item 
  •   Home
  • Recerca
  • Matemàtica
  • Articles publicats (Matemàtica)
  • View Item
  •   Home
  • Recerca
  • Matemàtica
  • Articles publicats (Matemàtica)
  • View Item
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
View/Open
Article (431.4Kb)
Issue date
2016
Author
Dalfó, Cristina
Huemer, Clemens
Salas Piñón, Julián
Suggested citation
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.
Impact


Web of Science logo    citations in Web of Science

Scopus logo    citations in Scopus

Google Scholar logo  Google Scholar
Share
Export to Mendeley
Metadata
Show full item record
Abstract
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
Is part of
Electronic Journal of Combinatorics, 2016, vol. 23, núm. 1
European research projects
Collections
  • Articles publicats (Matemàtica) [358]
  • Publicacions de projectes de recerca del Plan Nacional [2953]

Contact Us | Send Feedback | Legal Notice
© 2023 BiD. Universitat de Lleida
Metadata subjected to 
 

 

Browse

All of the repositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

Statistics

View Usage Statistics

D'interès

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

Contact Us | Send Feedback | Legal Notice
© 2023 BiD. Universitat de Lleida
Metadata subjected to