4
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Brendan McKay Jan 15 '16 at 22:24
  • 1
    $\begingroup$ $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. $\endgroup$ – Brendan McKay Jan 15 '16 at 23:13
  • 1
    $\begingroup$ $R=D=7$ for some dual-fullerenes on 68 vertices. It appears likely that most dual-fullerenes fail the inequality. $\endgroup$ – Brendan McKay Jan 16 '16 at 0:11
  • $\begingroup$ Thank you Andrew for the answer, and Brendan for the experiments! $\endgroup$ – verifying Jan 17 '16 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.