2025/07/03 by An, Ran, Li, Hengzhe, Liu, Jianbing +1
#05C07 #05C12 #05C20 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2507.02277
In 2018, Dankelmann, Gao, and Surmacs [J. Graph Theory, 88(1): 5--17, 2018] established sharp bounds on the oriented diameter of a bridgeless undirected graph and a bridgeless undirected bipartite graph in terms of vertex degree. In this paper, we extend these results to mixed graphs, which contain both directed and undirected edges.
Let the undirected degree d^*G(x) of a vertex x ∈ V(G) be the number of its incident undirected edges in a mixed graph G of order n, and let the maximum undirected degree be Δ^*(G) = max\d^*G(v) : v ∈ V(G)\. We prove that (1) amp; \overrightarrowdiam(G) ≤ n - Δ^* + 3 amp;amp; if G is undirected, or contains a vertex u with d^*G(u) = Δ^*
amp; amp;amp; and d+G(u) + d-G(u) ≥ 2, or Δ^* = 5 and d+G(u) + d-G(u) = 1;
(2) amp; \overrightarrowdiam(G) ≤ n - Δ^* + 4 amp;amp; otherwise. We also establish bounds for mixed bipartite graphs. If G is a bridgeless mixed bipartite graph with partite sets A and B, and u ∈ B, then (1) amp; \overrightarrowdiam(G) ≤ 2(|A| - d(u)) + 7 amp;amp; if G is undirected;
(2) amp; \overrightarrowdiam(G) ≤ 2(|A| - d^*(u)) + 8 amp;amp; if d+G(u) + d-G(u) ≥ 2;
(3) amp; \overrightarrowdiam(G) ≤ 2(|A| - d^*(u)) + 10 amp;amp; otherwise.
All of the above bounds are sharp, except possibly the last one.