To access the full text documents, please follow this link: http://hdl.handle.net/2117/24097

The degree-diameter problem in maximal bipartite planar graphs
Dalfó Simó, Cristina; Huemer, Clemens; Salas, Julian
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions; Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta
The (A ,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 (A ,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 ( A ,D) and obtain that an upper bound on n is approximately 3(2D+1)( -2)bD/2c, and another one is C( - 2)bD/2c if D and C is a sufficiently large constant. Our upper bounds 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.
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs
Graph theory
Maximal planar bipartite graphs
Grafs, Teoria de
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
info:eu-repo/semantics/conferenceObject
         

Show full item record

Related documents

Other documents of the same author

Dalfó Simó, Cristina; Huemer, Clemens; Salas Piñon, Julián
Fabila-Monroy, Ruy; Huemer, Clemens; Tramuns, Eulàlia
Barrière Figueroa, Eulalia; Huemer, Clemens
Fabila Monroy, Ruy; Huemer, Clemens; Mitsche, Dieter
Fabila-Monroy, Ruy; Huemer, Clemens; Mitsche, Dieter
 

Coordination

 

Supporters