• https://mat.upc.edu/ca/activitats/computational-geometry-seminar
• Computational Geometry Seminar. Clemens Huemer : The degree/diameter problem in maximal planar bipartite graphs.
• 2015-12-04T12:30:00+01:00
• 2015-12-04T13:30:00+01:00
• Friday, December 4, 2015, 12:30-13:30 (15 minutes delayed with respect to the usual schedule) Room S215 Omega Building, Campus Nord UPC (equiv.: Room 215 Floor -2)

Friday, December 4, 2015, 12:30-13:30 (15 minutes delayed with respect to the usual schedule) Room S215 Omega Building, Campus Nord UPC (equiv.: Room 215 Floor -2)

Quan

04/12/2015 de 12:30 a 13:30

On

Room S215 Omega Building, Campus Nord UPC

Nom de contacte

Clemens Huemer

URL de l'esdeveniment

Lloc web relacionat

Afegeix un esdeveniment al calendari

iCal

Abstract: The $(\Delta,D)$ (degree/diameter) problem consists of finding the largest possible number of vertices $n$
among all the graphs with maximum degree $\Delta$ and diameter $D$. We consider the $(\Delta,D)$ problem for
maximal planar bipartite graphs, that is, simple planar graphs in which every face is a quadrangle.
We obtain that for the $(\Delta,2)$ problem, the number of vertices is $n=\Delta+2$; and for the $(\Delta,3)$ problem,
$n= 3\Delta-1$ if $\Delta$ is odd and $n= 3\Delta-2$ if $\Delta$ is even. Then, we prove that, for the general case of the
$(\Delta,D)$ problem, an upper bound on $n$ is approximately $3(2D+1)(\Delta-2)^{\lfloor D/2\rfloor}$, and another one
is $C(\Delta-2)^{\lfloor D/2\rfloor}$ if $\Delta\geq 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 $(\Delta-2)^{k}$ if $D=2k$, and $3(\Delta-3)^k$
if $D=2k+1$, for $\Delta$ and $D$ sufficiently large in both cases.
This is a joint work with Cristina Dalfó and Julián Salas.