# Diameter vs Radius in Maximal Planar Graphs

Let $G$ be an undirected graph.

• The eccentricity of a vertex $v$ of $G$, is the maximum distance between $v$ and any other vertex of $G$:$\;\;$ $\mathit{ecc}(v) = \max_{u}\mathit{dist}(v,u)$.
• The radius of $G$ is the minimum eccentricity of a vertex of $G$:$\;\;$$R(G) = \min_v \mathit{ecc}(v). • The diameter of G is the maximum eccentricity of a vertex of G: \;\; D(G) = \max_v \mathit{ecc}(v). Question: Clearly we have R(G)\leq D(G). Is it possible to improve this upper-bound of R(G) in function of D(G) on maximal planar graphs? For instance, if G is outerplanar, then it is known that R(G)\leq \lfloor\frac{D(G)}{2}\rfloor + 1. Is the same relation valid for maximal planar graphs? Obs1: An outerplanar graph is a planar graph which can be drawn in the plane in such a way that no two edges cross and all vertices belong to the outer-face of the drawing. Obs2: A maximal planar (outerplanar) graph is a planar (outerplanar) graph whose addition of one edge destroys the property of being planar (outerplanar). ## 1 Answer The inequality$$R(G)\leq \lfloor\frac{D(G)}{2}\rfloor + 1$$does not hold in general for maximal planar graphs. For a counterexample, let$G$be the icosahedral graph. Every face of the icosahedron is a triangle, and a planar graph is maximal if and only if it is a triangulation, so$G$is a maximal planar graph. The radius and diameter of$G$are both$3$, but the inequality above would require$R(G) \leq 2$. I don't know what the best general upper bound is for maximal planar graphs. • In fact the icosahedron (with 12 vertices) is the unique smallest counterexample. There are two with$R=D=3$on 13 vertices, 29 on 14 vertices, 378 on 15 vertices and 6517 with 16 vertices. Up to 16 vertices the only parameters failing the conjecture are$R=D=3$. – Brendan McKay Jan 15 '16 at 22:24 •$R=D=4$occurs for two dual-fullerenes (planar triangulations with vertices of degree only 5 and 6) on 22 vertices. Continuing with fullerenes,$R=4,D=5$occurs on 26 vertices and$R=D=5$occurs at 32 vertices and$R=D=6$occurs at 48 vertices. I expect$R=D=k$is possible for all$k$but I don't have a proof. – Brendan McKay Jan 15 '16 at 23:13 •$R=D=7\$ for some dual-fullerenes on 68 vertices. It appears likely that most dual-fullerenes fail the inequality. – Brendan McKay Jan 16 '16 at 0:11
• Thank you Andrew for the answer, and Brendan for the experiments! – verifying Jan 17 '16 at 21:34