Oriented diameter of graphs with diameter $4$ and given edge girth

Abstract

Let $f(d)$ be the smallest value for which every bridgeless graph $G$ with diameter $d$ admits a strong orientation $\overrightarrow{G}$ such that the diameter of $\overrightarrow{G}$ is at most $f(d)$. Chvátal and Thomassen (JCT-B, 1978) obtained general bounds for $f(d)$ and proved that $f(2)=6$. Kwok et al. (JCT-B, 2010) proved that $9\le f(3)\le 11$. Wang and Chen (JCT-B, 2022) determined $f(3)=9$. Babu et al. (DAM, 2021) showed $f(4)\le 21$. In this paper, we introduce a new approach to studying $f(d)$ via the edge girth of a bridgeless graph $G$, denoted by $g^{\ast }(G)=\max \{l_G(e)\mid e\in E(G)\}$, where $l_G(e)$ is the length of the shortest cycle containing $e$ in $G$. Then we define $F(d,g^{\ast })=\max \{\overrightarrow{diam}(G)\mid G\text{ is bridgeless},d(G)=d,g^{\ast }(G)=g^{\ast }\}$, and show $f(d)=\max \{F(d,g^{\ast })\mid 2\le g^{\ast }\le 2d+1\}$. As the main result of this paper, we establish $F(4,2)=4$, $F(4,9)=12$, $F(4,3)\le 12$, and $F(4,g^{\ast })\le 13$ for $g^{\ast }\in \{6,7,8\}$, and we propose two open problems for further research.

36 pages, 6 figures