5
$\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).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .