2025/07/31 by Jifu Lin, Lihua You, Lin, Jifu +1
Computer Science · #05C12 #05C20 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2507.23517
openalex publication_date 2025/07/31 · openalex created_date 2025/10/08 · openalex updated_date 2026/07/28
Let f(d) be the smallest value for which every bridgeless graph G with diameter d admits a strong orientation \overrightarrowG such that the diameter of \overrightarrowG 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≤ f(3)≤ 11. Wang and Chen (JCT-B, 2022) determined f(3)=9. Babu et al. (DAM, 2021) showed f(4)≤ 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\lG(e)| e∈ E(G)\, where lG(e) is the length of the shortest cycle containing e in G. Then we define F(d,g^*)=max\\overrightarrowdiam(G)| G is bridgeless,d(G)=d,g^*(G)=g^*\, and show f(d)=max\F(d,g^*)| 2≤ g^*≤ 2d+1\. As the main result of this paper, we establish F(4,2)=4, F(4,9)=12, F(4,3)≤ 12, and F(4,g^*)≤ 13 for g^*∈\6,7,8\, and we propose two open problems for further research.