6
$\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$

2 Answers 2

Reset to default
5
$\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$ 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$ 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$ Commented Jan 16, 2016 at 0:11
  • 1
    $\begingroup$ Thank you Andrew for the answer, and Brendan for the experiments! $\endgroup$ Commented Jan 17, 2016 at 21:34
3
$\begingroup$

The answer seems to be $R(G)\leq \frac{1}{2} D(G) + O(\sqrt{n})$ and this is tight for some maximal planar graphs.

Reference

Therese Biedl, Debajyoti Mondal "Improved Outerplanarity Bounds for Planar Graphs", July 2024, arXiv:2407.04282.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.