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\leq f(3)\leq 11$. Wang and Chen (JCT-B, 2022) determined $f(3)=9$. Babu et al. (DAM, 2021) showed $f(4)\leq 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^*(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^*)=\max\{\overrightarrow{diam}(G)\mid G\text{ is bridgeless},d(G)=d,g^*(G)=g^*\}$, and show $f(d)=\max\{F(d,g^*)\mid 2\leq g^*\leq 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^*)\le 13$ for $g^*\in\{6,7,8\}$, and we propose two open problems for further research.
From: Lihua You [view email]
[v1]
Thu, 31 Jul 2025 13:00:38 UTC (85 KB)
[v2]
Tue, 28 Oct 2025 08:53:55 UTC (280 KB)
[v3]
Sun, 14 Jun 2026 13:05:11 UTC (280 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。