This paper demonstrates specific bounds for strong orientations in bridgeless graphs, revealing insights into diameter properties.
Let G be a bridgeless graph. We introduce the maximum edge girth of G, denoted by g^*(G)=max(e) e∈ E(G)\, where lG(e) is the edge girth of e, defined as the length of the shortest cycle containing e. Let $F(d,A)$ be the smallest value for which every bridgeless graph G with diameter d and g^*(G)∈ A admits a strong orientation G such that the diameter of G is at most $F(d,A)$. Let $f(d)=F(d,A)$, where A=∈ N 2≤ a≤ 2d+1\. Chvátal and Thomassen (JCT-B, 1978) obtained general bounds for $f(d)$ and showed that $f(2)=6$. Kwok et al. (JCT-B, 2010) proved that 9≤ f(3)≤ 11. Wang and Chen (JCT-B, 2022) determined $f(3)=9$. In this paper, we give that 12≤ F(4,A^*)≤ 13, where A^*=\2,3,6,7,8,9\.
No takes yet. Share an insight, caveat, or question.
Lin et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: