Downloads provided by UsageCounts
handle: 2117/89907 , 2117/26448 , 10261/132344 , 10459.1/72566
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.
Teoria de, Maximal planar bipartite graphs, Grafs, Teoria de, Planar bipartite graphs, Planar graphs, Classificació AMS::05 Combinatorics::05C Graph theory, (¿,D) problem, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs, Degree/diameter Problem, Graph theory, Grafs, Degree/diameter problem, Δ, D problem, maximal planar bipartite graphs, :05 Combinatorics::05C Graph theory [Classificació AMS], Bipartite graphs, :Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC]
Teoria de, Maximal planar bipartite graphs, Grafs, Teoria de, Planar bipartite graphs, Planar graphs, Classificació AMS::05 Combinatorics::05C Graph theory, (¿,D) problem, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs, Degree/diameter Problem, Graph theory, Grafs, Degree/diameter problem, Δ, D problem, maximal planar bipartite graphs, :05 Combinatorics::05C Graph theory [Classificació AMS], Bipartite graphs, :Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC]
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
| views | 142 | |
| downloads | 410 |

Views provided by UsageCounts
Downloads provided by UsageCounts