Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: http://hdl.handle.net/2117/26448

The degree/diameter problem in maximal planar bipartite graphs
Dalfó Simó, Cristina; Huemer, Clemens; Salas Piñon, Julián
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 (¿;D) (degree/diameter) problem consists of nding 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.
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs
Graph theory
(¿
D) problem
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
Article
         

Mostra el registre complet del document

Documents relacionats

Altres documents del mateix autor/a

Dalfó Simó, Cristina; Huemer, Clemens; Salas Piñon, Julián
Dalfó Simó, Cristina; Huemer, Clemens; Salas, Julian
Böhmová, Katerina; Dalfó Simó, Cristina; Huemer, Clemens
Fabila-Monroy, Ruy; Huemer, Clemens; Tramuns, Eulàlia