Back to Search
Start Over
On the oriented diameter of near planar triangulations
- Publication Year :
- 2023
-
Abstract
- In this paper, we show that the oriented diameter of any $n$-vertex $2$-connected near triangulation is at most $\lceil{\frac{n}{2}}\rceil$ (except for seven small exceptions), and the upper bound is tight. This extends a result of Wang et.al. on the oriented diameter of maximal outerplanar graphs, and improves an upper bound of $n/2+O(\sqrt{n})$ on the oriented diameter of planar triangulations by Mondal, Parthiban and Rajasingh.
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2312.03258
- Document Type :
- Working Paper