科研速览 · Science Skim继续刷下去 · Keep skimming →
◇ arXiv2026-08-19· math.CO

Improved bounds on the oriented diameter of planar triangulations

Xiaonan Liu

原始摘要(英文原文)· Original abstract
The oriented diameter of a connected bridgeless graph $G$, denoted by $\overrightarrow{\operatorname{diam}}(G)$, is the minimum diameter among all strong orientations of $G$. We study the oriented diameter of planar triangulations, and show that $\overrightarrow{\operatorname{diam}}(G)\leq \frac{2n+44}{5}$ for any $n$-vertex planar triangulation $G$. This improves the leading constant in the previous best general upper bound $\lceil \frac{n}{2}\rceil$, due to Ge, Liu, and Wang, from $1/2$ to $2/5$. We also prove that every $n$-vertex $4$-connected planar triangulation satisfies $\overrightarrow{\operatorname{diam}}(G)\leq \frac{n+17}{3}$.
读原文 · Read the paper ↗

AI 追问PRO

登录后使用 AI 追问

讨论区

登录后参与讨论

相关论文 · Related

Improved bounds on the oriented diameter of planar triangulations — 科研速览 Science Skim