Loading...
Loading...

Go to the content (press return)

The degree/diameter problem in maximal planar bipartite graphs

Author
Dalfo, C.; Huemer, C.; Salas, J.
Type of activity
Journal article
Journal
Electronic journal of combinatorics
Date of publication
2016
Volume
23
Number
1
First page
1
Last page
23
Project funding
GRUP DE RECERCA EN GEOMETRIA COMPUTACIONAL I MATEMÀTICA DISCRETA. 2014SGR46.
Tecnicas de optimizacion en teoria de grafos, grupos y combinatoria. aplicaciones a redes, algoritmos y protocolos de comunicacion.
Repository
http://hdl.handle.net/2117/89907 Open in new window
URL
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p60/pdf Open in new window
Abstract
The (¿,D)(¿,D) (degree/diameter) problem consists of finding the largest possible number of vertices nn among all the graphs with maximum degree ¿¿ and diameter DD. We consider the (¿,D)(¿,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)(¿,2) problem, the number of vertices is n=¿+2n=¿+2; and for the (¿,3)(¿,3) problem, n=3¿-1n=3¿-1 if ¿¿ is odd and n=3¿-2n=3¿-2 if ¿¿ is even. Then,...
Citation
Dalfo, C., Huemer, C., Salas, J. The degree/diameter problem in maximal planar bipartite graphs. "Electronic journal of combinatorics", 2016, vol. 23, núm. 1, p. 1-23.
Keywords
Bipartite graphs, Degree/diameter Problem, Planar graphs
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications
DCG - Discrete and Combinatorial Geometry

Participants

Attachments