|
| Oriented Diameter and Radius ofTriangulations |
| Xiaolin Wang |
| (School of Mathematics and Statistics, Fuzhou University, Fuzhou 350108,
China) |
| DOI： |
| Abstract: |
| Denote $\rbjt{diam}(G)$ ($\rbjt{rad}(G)$) as the minimum directed diameter (radius) among all orientations of the bridgeless graph $G$. Denote $G$ as a triangulation with $n$ vertices.
Mondal, Parthiban and Rajasingh proved that $\rbjt{diam}(G) \leq \frac{n}{2}+O(\sqrt{n})$. Ge, Liu and Wang improved it to $\frac{n}{2}$. In this paper, we first prove that $\rbjt{rad}(G)\leq 2r$, where $r$ is the radius of $G$. We also prove that for $s$-connected triangulation $G$, there exists an integer $c$ such that $ \rbjt{rad}(G) \leq \frac{n}{s} +c$.
As a corollary, we improve the upper bound of the oriented diameter of 5-connected triangulations to $\frac{2n}{5} +c$. Furthermore, we prove that under some connecting condition of the triangulation $G$, $\rbjt{rad}(G)\leq r+1$, where $r$ is the radius of $G$. Then for $s$-connected triangulation $G$ under some connecting condition, there exists an integer $c$ such that $ \rbjt{rad}(G) \leq \frac{n}{2s} +c$ and $ \rbjt{diam}(G) \leq \frac{n}{s} +c$, which are tight apart from a constant. |
| Key words: Oriented radius, Oriented diameter, Triangulation. |